AGILE: adaptive indexing for context-aware information filters

ABSTRACT

Information filtering has become a key technology for modern information systems. The goal of an information filter is to route messages to the right recipients (possibly none) according to declarative rules called profiles. In order to deal with high volumes of messages, several index structures have been proposed in the past. The challenge addressed in this paper is to carry out stateful information filtering in which profiles refer to values in a database or to previous messages. The difficulty is that database update streams need to be processed in addition to messages. This paper presents AGILE, a way to extend existing index structures so that the indexes adapt to the message/update workload and show good performance in all situations. Performance experiments show that AGILE is overall the clear winner as compared to the best existing approaches. In extreme situations in which it is not the winner, the overheads are small.

REFERENCES

• 1: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: Richard R. Brooks , S. S. Iyengar, Multi-sensor fusion: fundamentals and applications with software, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 4: H.-J. Cho, J.-K. Min, and C.-W. Chung. An Adaptive Indexing Technique Using Spatio-Temporal Query Workloads. Information and Software Technology, 46(4):229--241, 2004.
• 5: O. Cooper, A. Edakkunni, M. J. Franklin, W. Hong, S. R. Jeffery, S. Krishnamurthy, F. Reiss, S. Rizvi, and E. Wu. HiFi: A Unified Architecture for High Fan-in Systems. In VLDB, 2004.
• 6: Anind K. Dey, Understanding and Using Context, Personal and Ubiquitous Computing, v.5 n.1, p.4-7, February 2001 [doi>10.1007/s007790170019 ]
• 7: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 8: Patrick Th. Eugster , Pascal A. Felber , Rachid Guerraoui , Anne-Marie Kermarrec, The many faces of publish/subscribe, ACM Computing Surveys (CSUR), v.35 n.2, p.114-131, June 2003 [doi>10.1145/857076.857078]
• 9: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 10: Peter M. Fischer , Donald Kossmann, Batched Processing for Information Filters, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.902-913, April 05-08, 2005 [doi>10.1109/ICDE.2005.25]
• 11: Andrew R. Golding , Neal Lesh, Indoor Navigation Using a Diverse Set of Cheap, Wearable Sensors, Proceedings of the 3rd IEEE International Symposium on Wearable Computers, p.29, October 18-19, 1999
• 12: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: Eric N. Hanson , Theodore Johnson, Selection predicate indexing for active databases using interval skip lists, Information Systems, v.21 n.3, p.269-298, May 1996 [doi>10.1016/0306-4379(96)00015-4 ]
• 14: M. L. Lee, W. Hsu, C. S. Jensen, B. Cui, and K. L. Teo. Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In VLDB, 2003.
• 15: Beng Chin Ooi , Kian Lee Tan , Cui Yu, Frequent Update and Efficient Retrieval: an Oxymoron on Moving Object Indexes?, Proceedings of the Third International Conference on Web Information Systems Engineering (Workshops) - (WISEw'02), p.3, December 11-11, 2002
• 16: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 17: Praveen Seshadri , Arun N. Swami, Generalized Partial Indexes, Proceedings of the Eleventh International Conference on Data Engineering, p.420-427, March 06-10, 1995
• 18: M. Stonebraker, The case for partial indexes, ACM SIGMOD Record, v.18 n.4, p.4-11, Dec. 1989 [doi>10.1145/74120.74121]
• 19: Y. Tao and D. Papadias. Adaptive Index Structures. In VLDB, 2002.
• 20: Mark Weiser, Some computer science issues in ubiquitous computing, Communications of the ACM, v.36 n.7, p.75-84, July 1993 [doi>10.1145/159544.159617]
• 21: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]
• 22: Y. Yao and J. Gehrke. Query Processing in Sensor Networks. In CIDR, 2003.