Connections: using context to enhance file search

ABSTRACT

Connections is a file system search tool that combines traditional content-based search with context information gathered from user activity. By tracing file system calls, Connections can identify temporal relationships between files and use them to expand and reorder traditional content search results. Doing so improves both recall (reducing false-positives) and precision (reducing false-negatives). For example, Connections improves the average recall (from 13% to 22%) and precision (from 23% to 29%) on the first ten results. When averaged across all recall levels, Connections improves precision from 17% to 28%. Connections provides these benefits with only modest increases in average query time (2 seconds), indexing time (23 seconds daily), and index size(under 1% of the user's data set).

REFERENCES

• 1: N. Abdul-Jaleel, A. Corrada-Emmanuel, Q. Li, X. Liu, C. Wade, and J. Allan. UMass at TREC 2003: HARD and QA. Text Retrieval Conference, pages 715--725, 2003.
• 2: A. Amer, D. Long, J.-F. Paris, and R. Burns. File access prediction with adjustable accuracy. International Performance Conference on Computers and Communication. IEEE, 2002.
• 3: Akshat Aranya , Charles P. Wright , Erez Zadok, Tracefs: A File System to Trace Them All, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 6: Scott Fertig , Eric Freeman , David Gelernter, Lifestreams: an alternative to the desktop metaphor, Conference companion on Human factors in computing systems: common ground, p.410-411, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/257089.257404]
• 7: Jim Gemmell , Gordon Bell , Roger Lueder , Steven Drucker , Curtis Wong, MyLifeBits: fulfilling the Memex vision, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641053]
• 8: Dominic Giampaolo, Practical File System Design with the Be File System, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 9: David K. Gifford , Pierre Jouvelot , Mark A. Sheldon , James W. O'Toole, Jr., Semantic file systems, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.16-25, October 13-16, 1991, Pacific Grove, California, United States
• 10: Google, http://www.google.com/.
• 11: Google Desktop, http://desktop.google.com/.
• 12: Burra Gopal , Udi Manber, Integrating content-based access mechanisms with hierarchical file systems, Proceedings of the third symposium on Operating systems design and implementation, p.265-278, February 1999, New Orleans, Louisiana, United States
• 13: J. Griffioen and R. Appleton. Reducing file system latency using a predictive approach. Summer USENIX Technical Conference, pages 197--207. USENIX Association, 1994.
• 14: Grokker, http://www.grokker.com/.
• 15: T. H. Haveliwala. Topic-sensitive PageRank: a context-sensitive ranking algorithm for web search. IEEE Transactions on Knowledge and Data Engineering, 15(4):784--796. IEEE, August 2003.
• 16: B. Hayes. Terabyte territory. American Scientist, 90(3):212--216, May--June 2002.
• 17: E. Horvitz, J. Breese, D. Heckerman, D. Hovel, and K. Rommelse. The Lumiere project: bayesian user modeling for inferring the goals and needs of software users. Conference on Uncertainty in Artificial Intelligence, pages 256--265, 1998.
• 18: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 19: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 20: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 21: T. M. Kroeger and D. D. E. Long. Predicting file system actions from prior events. USENIX Annual Technical Conference, pages 319--328. USENIX Association, 1996.
• 22: G. H. Kuenning. Seer: predictive file hoarding for disconnected mobile operation. Technical Report UCLA--CSD--970015. University of California, Los Angeles, May 1997.
• 23: L. S. Larkey, J. Allan, M. E. Connell, A. Bolivar, and C. Wade. UMass at TREC 2002: cross language and novelty tracks. Text Retrieval Conference, 2002.
• 24: H. Lei and D. Duchamp. An analytical approach to file prefetching. USENIX Annual Technical Conference. USENIX Association,, 1997.
• 25: The Lemur Toolkit, http://www.lemurproject.org/.
• 26: Lycos, http://www.lycos.com/.
• 27: T. M. Madhyastha , D. A. Reed, Intelligent, adaptive file system policy selection, Proceedings of the 6th Symposium on the Frontiers of Massively Parallel Computation, p.172, March 27-31, 1996
• 28: U. Manber, M. Smith, and B. Gopal. WebGlimpse: combining browsing and searching. USENIX Annual Technical Conference. USENIX Association, 1997.
• 29: U. Manber and S. Wu. GLIMPSE: a tool to search through entire file systems. Winter USENIX Technical Conference, pages 23--32. USENIX Association, 1994.
• 30: Michael L. Mauldin, Retrieval performance in Ferret a conceptual information retrieval system, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.347-355, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122896]
• 31: Donald Metzler , W. Bruce Croft, Combining the language model and inference network approaches to retrieval, Information Processing and Management: an International Journal, v.40 n.5, p.735-750, September 2004 [doi>10.1016/j.ipm.2004.05.001]
• 32: D. Metzler, T. Strohman, H. Turtle, and W. B. Croft. Indri at TREC 2004: terabyte track. Text Retrieval Conference, 2004.
• 33: M. A. Olson, K. Bostic, and M. Seltzer. Berkeley DB. Summer USENIX Technical Conference. USENIX Association, 1999.
• 34: D. Quan, D. Huynh, and D. R. Karger. Haystack: a platform for authoring end user semantic web applications. International Semantic Web Conference, 2003.
• 35: Bradley Rhodes, Using Physical Context for Just-in-Time Information Retrieval, IEEE Transactions on Computers, v.52 n.8, p.1011-1014, August 2003 [doi>10.1109/TC.2003.1223636]
• 36: B. Rhodes and T. Starner. The Remembrance Agent: a continuously running automated information retrieval system. International Conference on The Practical Application of Intelligent Agents and Multi Agent Technology, pages 487--495, 1996.
• 37: S. Sechrest and M. McClennen. Blending hierarchical and attribute-based file naming. International Conference on Distributed Computing Systems, pages 572--580, 1992.
• 38: Jaime Teevan , Christine Alvarado , Mark S. Ackerman , David R. Karger, The perfect search engine is not enough: a study of orienteering behavior in directed search, Proceedings of the SIGCHI conference on Human factors in computing systems, p.415-422, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985745]
• 39: Jaime Teevan , Susan T. Dumais , Eric Horvitz, Personalizing search via automated analysis of interests and activities, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076111]
• 40: Terrier Information Retrieval Platform, http://ir.dcs.gla.ac.uk/terrier/.
• 41: Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
• 42: E. M. Voorhees. Overview of TREC 2003. Text Retrieval Conference. NIST, 2003.
• 43: Merriam-Webster OnLine, http://www.m-w.com/.
• 44: X1 Desktop Search, http://www.x1.com/.
• 45: Yahoo!, http://www.yahoo.com/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

General Terms:
Algorithms, Design, Human Factors, Management

Keywords:
context, file system search, successor models