Facilitating discovery on the private web using dataset digests

ABSTRACT

Whereas strategies for discovering content on the surface web are commonplace, similar strategies for the private web are nonexistent. In this paper we first establish a formal framework for advertising the existence of private web resources that subsumes many existing summarization strategies based on succinct statistical summaries (which we call digests). We then investigate the tradeoff between the data owners' desires to minimize disclosure and the searchers' desires to minimize query error, demonstrating that our techniques are superior to k-anonymity. Finally, we show that our techniques for summarization do, in fact, make it possible to discover private web data resources.

REFERENCES

• 1: "Neuroscience Information Framework," http://neurogateway.org/.
• 2: J. Callan, "Distributed Information Retrieval," in Advances in Information Retrieval, W. B. Croft, Ed.: Kluwer Academic Publishers, 2000, pp. 127--150.
• 3: A. P. Dempster, N. M. Laird, and D. B. Rubin, "Maximum Likelihood from Incomplete Data via the EM algorithm," Journal of the Royal statistical Society, vol. 39, pp. 1--38, 1977.
• 4: N. Fost and R. J. Levine, "The Dysregulation of Human Subjects Research," Journal of the American Medical Association, vol. 298, pp. 2196--2198, 2007.
• 5: M. Y. Galperin, "The Molecular Biology Database Collection: 2008 update," http://www3.oup.co.uk/nar/database/c/.
• 6: D. Gardner, A. W. Toga, G. Ascoli, J. Beatty, J. F. Brinkley, A. Dale, P. Fox, E. Gardner, J. George, N. Goddard, K. Harris, E. Herskovits, M. Hines, G. Jacobs, R. Jacobs, E. Jones, D. Kennedy, D. Kimberg, J. Mazziotta, P. Miller, S. Mori, D. Mountain, A. Reiss, G. Rosen, D. Rottenberg, G. Shepherd, N. Smalheiser, K. Smith, T. Strachan, D. Van Essen, R. Williams, and S. Wong, "Towards Effective and Rewarding Data Sharing," NeuroInformatics, vol. 1, pp. 289--296, 2003.
• 7: Luis Gravano , Chen-Chuan K. Chang , Héctor García-Molina , Andreas Paepcke, STARTS: Stanford proposal for Internet meta-searching, ACM SIGMOD Record, v.26 n.2, p.207-218, June 1997
• 8: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 9: N. Hamilton, "The Mechanics of a Deep Net Metasearch Engine," http://turbo10.com/papers/deepnet.pdf.
• 10: Bin He , Mitesh Patel , Zhen Zhang , Kevin Chen-Chuan Chang, Accessing the deep web, Communications of the ACM, v.50 n.5, p.94-101, May 2007 [doi>10.1145/1230819.1241670]
• 11: Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, ACM SIGMOD Record, v.20 n.2, p.268-277, June 1991
• 12: Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
• 13: Panagiotis G. Ipeirotis , Luis Gravano , Mehran Sahami, Probe, count, and classify: categorizing hidden web databases, ACM SIGMOD Record, v.30 n.2, p.67-78, June 2001
• 14: L. Kaufman and P. J. Rousseuw, Finding Groups in Data: An Introduction to Cluster Analysis: Wiley, 1990.
• 15: S. H. Koslow, "Sharing Primary Data: A Threat or Asset to Discovery?," Nature Reviews Neuroscience, vol. 3, pp. 311--313, 2002.
• 16: Carl Lagoze , Herbert Van de Sompel, The open archives initiative: building a low-barrier interoperability framework, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.54-62, January 2001, Roanoke, Virginia, United States [doi>10.1145/379437.379449]
• 17: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 18: Library of Congress, "Search/Retrieval via URL," http://www.loc.gov/standards/sru/.
• 19: Automatic Information Discovery from the "Invisible Web", Proceedings of the International Conference on Information Technology: Coding and Computing, p.332, April 08-10, 2002
• 20: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 21: R. B. Ness, "Influence of the HIPAA Privacy Rule on Health Research," Journal of the American Medical Association, vol. 298, pp. 2164--2170, 2007.
• 22: NIH, "NIH Policy on data sharing," http://grants2.nih.gov/grants/policy/data_sharing.
• 23: Alexandros Ntoulas , Petros Zerfos , Junghoo Cho, Downloading textual hidden web content through keyword queries, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA [doi>10.1145/1065385.1065407]
• 24: J. Qiu, F. Shao, M. Zatsman, and J. Shanmugasundaram, "International Workshop on Web and Databases," in WebDB, San Diego, CA, 2003, pp. 79--86.
• 25: Sriram Raghavan , Hector Garcia-Molina, Crawling the Hidden Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.129-138, September 11-14, 2001
• 26: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 27: J. P. Stenbit, "Department of Defense Net-Centric Data Strategy," http://www.defenselink.mil/nii/org/cio/doc/Net-Centric-Data-Strategy-2003-05-092.pdf.
• 28: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 29: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, ACM SIGMOD Record, v.25 n.2, p.103-114, June 1996
• 30: G. K. Zipf, Human Behavior and the Principle of Least Effort. Reading, MA: Addison-Wesley, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
dataset discovery, disclosure, private web, search engine, structured data