Abstract system administrators may specify various network packages which are suspicious due to different reasons (intruEfficiently processing continuous k-nearest neighbor sion, rule violation, misuse etc.) Then, the stream of netqueries on data streams is important in many application work packages is constantly surveyed for packages which domains, e. g. for network intrusion detection. Usually not are similar to the suspicious objects. As a second example, all valid data objects from the stream can be kept in main take advertisements of an arbitrary market segment. Each memory. Therefore, most existing solutions are approximauser may specify the properties (price, color, size, weight tive. In this paper, we propose an efficient methodfor exact etc.) of a product he/she is interested in. The system permak-NN monitoring. Our method is based on three ideas, (1) nently informs the user about those advertisements which fit selecting exactly those objects from the stream which are best his/her requirements. able to become the nearest neighbor of one or more continWe distinguish between two different types of similaruous queries and storing them in a skyline data structure, ity queries: range queries and nearest neighbor queries. (2) delaying to process those objects which are not immediFor both types, the user selects an object, the query obately nearest neighbors of any query, and (3) indexing the ject which is the starting point of the search. For a range queries rather than the streaming objects. In an extensive search, the user must additionally specify the query radius, experimental evaluation we demonstrate that our method is i.e. a threshold for the maximally allowed distance from the applicable on high throughput data streams requiring only query object. Since similarity measures are often not very very limited storage. intuitive, it may be difficult to specify such a query radius. Therefore, in practice, the k-nearest neighbor query (k-NN) is more important, because the user only has to specify k,
Another work relevant to ours is REF , which proposes an algorithm for continuous k-NN monitoring over data streams with limited memory.
Efficiently Processing Continuous k-NN Queries on Data Streams
2007 IEEE 23rd International Conference on Data Engineering
2007 IEEE 23rd International Conference on Data Engineering
Computer Science