Title :
On the Complexity of Classification Functions
Author_Institution :
Dept. of Comput. Sci. & Electron., Kyushu Inst. of Technol., Iizuka
Abstract :
A classification function is a multiple-valued input function specified by a set of rules, where each rule is a conjunction of range functions. The function is useful for packet classification for internet, network intrusion detection system, etc. This paper considers the complexity of range functions and classification functions represented by sum-of-products expressions of binary variables. It gives tighter upper bounds on the number of products for range functions.
Keywords :
Internet; computational complexity; content-addressable storage; multivalued logic circuits; telecommunication security; ternary logic; Internet; multiple-valued input function; network intrusion detection system; packet classification function complexity; range function complexity; sum-of-products binary variable expression; ternary content-addressable memory; Cams; Computer science; Hardware; IP networks; Intrusion detection; Minimization; Multivalued logic; Table lookup; Upper bound; Web and internet services; CAM; Internet; packet classification; sum-of-products expression;
Conference_Titel :
Multiple Valued Logic, 2008. ISMVL 2008. 38th International Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
978-0-7695-3155-7
DOI :
10.1109/ISMVL.2008.18
