@string{LNCS = "Lecture Notes in Computer Science"} @ARTICLE{Amsaleg:Local, AUTHOR = {L. Amsaleg and P. Gros}, TITLE = {Content-based retrieval using local descriptors: Problems and issues from a database perspective}, JOURNAL = {Pattern Analysis and Applications}, YEAR = 2001, VOLUME = 4, NUMBER = {2/3}, PAGES = {1--124} } @book{AntiTrust, author = "{Howitt~(dir.)},Peter", title = "{AntiTrust}", publisher = "MGM Home Entertainment", year = "2001", note = "North American DVD release of 2000 motion picture from MGM Pictures.", } @Article{Bozkaya:MVP, author = "Tolga Bozkaya and Meral Ozsoyoglu", title = "Indexing large metric spaces for similarity search queries", journal = "ACM Transactions on Database Systems", volume = "24", number = "3", pages = "361--404", month = sep, year = "1999", coden = "ATDSD3", ISSN = "0362-5915", bibdate = "Tue Sep 26 08:44:02 MDT 2000", url = "http://www.acm.org/pubs/citations/journals/tods/1999-24-3/p361-bozkaya/", abstract = "One of the common queries in many database applications is finding approximate matches to a given query item from a collection of data items. For example, given an image database, one may want to retrieve all images that are similar to a given query image. Distance-based index structures are proposed for applications where the distance computations between objects of the data domain are expensive (such as high-dimensional data) and the distance function is metric. In this paper we consider using distance-based index structures for similarity queries on large metric spaces. We elaborate on the approach that uses reference points (vantage points) to partition the data space into spherical shell-like regions in a hierarchical manner. We introduce the multivantage point tree structure (mvp-tree) that uses more than one vantage point to partition the space into spherical cuts at each level. In answering similarity-based queries, the mvp-tree also utilizes the precomputed (at construction time) distances between the data points and the vantage points.\par We summarize the experiments comparing mvp-trees to vp-trees that have a similar partitioning strategy, but use only one vantage point at each level and do not make use of the precomputed distances. Empirical studies show that the mvp-tree outperforms the vp-tree by 20\% to 80\% for varying query ranges and different distance distributions. Next, we generalize the idea of using multiple vantage points and discuss the results of experiments we have made to see how varying the number of vantage points in a node affects affects performance and how much is gained in performance by making use of precomputed distances. The results show that, after all, it may be best to use a large number of vantage points in an internal node in order to end up with a single directory node and keep as many of the precomputed distances as possible to provide more efficient filtering during search operations. Finally, we provide some experimental results that compare mvp-trees with M-trees, which is a dynamic distance-based index structure for metric domains.", } @techreport{Chavez:Intrinsic, author = "Edgar Ch{\'a}vez and Gonzalo Navarro", title = "Measuring the Dimensionality of General Metric Spaces", institution = "Department of Computer Science, University of Chile", year = 2000, number = "TR/DCC-00-1", } @Article{Ciaccia:Searching, author = "Paolo Ciaccia and Marco Patella", title = "Searching in metric spaces with user-defined and approximate distances", journal = "ACM Transactions on Database Systems", volume = "27", number = "4", pages = "398--437", month = dec, year = "2002", coden = "ATDSD3", ISSN = "0362-5915", } @Book{CLRS, author = "T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein", title = "Introduction to Algorithms.", publisher = "MIT Press", year = "2001" } @inproceedings{Coskun:Confusion, author = "Baris Coskun and Nasir Memon", title = "Confusion/Diffusion Capabilities of Some Robust Hash Functions", booktitle = "Proceedings of the 40th Annual Conference on Information Sciences and Systems {(CISS'06)}", publisher = "IEEE", year = "2006", } @inproceedings{Craver:SDMI, author = "Scott A. Craver and Min Wu and Bede Liu and Adam Stubblefield and Ben Swartzlander and Dan S. Wallach and Drew Dean and Edward W. Felten", title = "Reading Between the Lines: Lessons from the {SDMI} {Challenge}", booktitle = "4th International Information Hiding Workshop", month = apr # "~25--27,", year = 2001, address = "Pittsburgh, {PA}, {USA}", note = "Statement read in lieu of withdrawn paper. Online {\url{http://www.cs.princeton.edu/sip/sdmi/sdmimessage.txt}}", } @inproceedings{Damiani:Open, author = "E. Damiani and De Capitani di Vimercati, S. and S. Paraboschi and P. Samarai", title = "An Open Digest-based Technique for Spam Detection", booktitle = "2004 International Workshop on Security in Parallel and Distributed Systems", year = 2004, } @Article{Feigenbaum:Random, title = "Random-Self-Reducibility of Complete Sets", author = "Joan Feigenbaum and Lance Fortnow", pages = "994--1005", journal = "SIAM Journal on Computing", year = "1993", month = oct, volume = "22", number = "5", } @Article{Frances:Covering, author = "M. Frances and A. Litman", title = "On covering problems of codes", journal = "Theory of Computing Systems", pages = "113--119", year = "1997", number = "2", volume = "30", publisher = "Springer-Verlag", address = "New York", URL = "http://springerlink.metapress.com/openurl.asp?genre=article&issn=1432-4350&volume=30&issue=2&spage=113", cdate = "1970-01-01", mdate = "2005-08-18", } @Article{Grollmann:Complexity, title = "Complexity Measures for Public-Key Cryptosystems", author = "Joachim Grollmann and Alan L. Selman", pages = "309--335", journal = "SIAM Journal on Computing", year = "1988", month = apr, volume = "17", number = "2", preliminary = "FOCS::GrollmannS1984:495", } @Article{Karmarkar:New, title = "A new polynomial-time algorithm for linear programming", author = "Narendra Karmarkar", journal = "Combinatorica", year = "1984", number = "4", volume = "4", bibdate = "2003-01-02", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/combinatorica/combinatorica4.html#Karmarkar84", pages = "373--396", } @InProceedings{Korn:Influence, author = "Flip Korn and S. Muthukrishnan", title = "Influence sets based on reverse nearest neighbor queries", pages = "201--212", editor = "Weidong Chen and Jeffrey F. Naughton and Philip A. Bernstein", booktitle = "Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data {(SIGMOD'00)}", year = "2000", publisher = "ACM", } @Article{Kushilevitz:Efficient, author = "Eyal Kushilevitz and Rafail Ostrovsky and Yuval Rabani", title = "Efficient search for approximate nearest neighbor in high dimensional spaces", journal = "SIAM Journal of Computing", pages = "457--474", year = "2000", number = "2", volume = "30", keywords = "nearest neighbor search, data structures, random projections", editor = "M. Yannakakis", publisher = "Society for Industrial and Applied Mathematics", address = "Philadelphia, PA", URL = "http://dx.doi.org/10.1137/S0097539798347177", cdate = "2005-02-03", mdate = "2005-08-18", } @InProceedings{Indyk:Locality, author = "Piotr Indyk and Rajeev Motwani and Prabhakar Raghavan and Santosh Vempala", title = "Locality-preserving hashing in multidimensional spaces", pages = "618--625", booktitle = "Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing {(STOC'97)}", year = "1997", publisher = "ACM", } @InProceedings{Lynn:Positive, title = "Positive Results and Techniques for Obfuscation", editor = "Christian Cachin and Jan Camenisch", author = "Ben Lynn and Manoj Prabhakaran and Amit Sahai", pages = "20--39", booktitle = "Advances in Cryptology---{EUROCRYPT} 2004", year = "2004", } @Article{Matousek:Subexponential, author = "Ji{\v{r}}{\'\i} Matou{\v{s}}ek and Micha Sharir and Emo Welzl", title = "A Subexponential Bound for Linear Programming", journal = "Algorithmica", volume = "16", number = "4--5", pages = "498--516", year = "1996", CODEN = "ALGOEJ", ISSN = "0178-4617 (print), 1432-0541 (electronic)", MRclass = "90C08 (68Q25 68U05 90C27)", MRnumber = "MR1407586 (97f:90052)", bibdate = "Mon Jan 22 05:32:05 MST 2001", bibsource = "dblp-journals-algorithmica.bib; http://dblp.uni-trier.de/db/journals/algorithmica/algorithmica16.html#MatousekSW96; http://www.math.utah.edu/pub/tex/bib/index-table-a.html#algorithmica; MathSciNet database", fjournal = "Algorithmica. An International Journal in Computer Science", oldlabel = "MatousekSW96", xmldata = "ftp://ftp.informatik.uni-trier.de/pub/users/Ley/bib/records.tar.gz#journals/algorithmica/MatousekSW96", mrnumber-url = "http://www.ams.org/mathscinet-getitem?mr=97f%3a90052", } @Article{Megiddo:Linear, author = "Nimrod Megiddo", title = "Linear Programming in Linear Time When the Dimension Is Fixed", journal = "Journal of the ACM", volume = "31", number = "1", pages = "114--127", month = jan, year = "1984", CODEN = "JACOAH", ISSN = "0004-5411", bibdate = "Wed Jan 15 18:12:53 MST 1997", bibsource = "Compendex database", abstract = "It is demonstrated that the linear programming problem in d variables and n constraints can be solved in $O(n)$ time when d is fixed. This bound follows from a multidimensional search technique which is applicable for quadratic programming as well. There is also developed an algorithm that is polynomial in both n and d provided d is bounded by a certain slowly growing function of n.", acknowledgement = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|", classification = "921", journalabr = "J Assoc Comput Mach", keywords = "design of algorithms; genuinely polynomial time; linear programming; linear time algorithms; mathematical programming, linear; multidimensional search; prune-and-search; quadratic programming; smallest ball problem; worst-case analysis", } @InProceedings{Mitchell:Hard, author = "David G. Mitchell and Bart Selman and Hector J. Levesque", title = "Hard and Easy Distributions for {SAT} Problems", booktitle = "Proceedings of the Tenth National Conference on Artificial Intelligence", year = "1992", editor = "Paul Rosenbloom and Peter Szolovits", pages = "459--465", publisher = "AAAI Press", } @Article{Ross:Template, title = "From Template to Image: Reconstructing Fingerprints from Minutiae Points", author = "Arun Ross and Jidnya Shah and Anil K. Jain", journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence", year = "2007", number = "4", volume = "29", bibdate = "2007-06-05", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/pami/pami29.html#RossSJ07", pages = "544--560", URL = "http://dx.doi.org/10.1109/TPAMI.2007.1018", } @book{Schneier:Applied, author = "Bruce Schneier", title = "Applied Cryptography", year = 1996, publisher = "John Wiley {\&} Sons, Inc.", edition = "Second", } @InProceedings{Skala:Measuring, title = "Measuring the Difficulty of Distance-Based Indexing", author = "Matthew Skala", pages = "103--114", booktitle = "String Processing and Information Retrieval: 12th Internatio nal Conference {(SPIRE'05)}", editor = "Mariano P. Consens and Gonzalo Navarro", year = "2005", publisher = "Springer", } @incollection{Thurber:Do, author = "James Thurber", title = "Do You Want to Make Something Out of It?", booktitle = "Thurber Country", chapter = 13, publisher = "Simon and Schuster", address = "New York", year = 1953, } @article{Uhlmann:GHTree, author = "Jeffrey K. Uhlmann", title = "Satisfying general proximity/similarity queries with metric trees", journal = "Information Processing Letters", year = 1991, volume = 40, pages = "175--179", month = nov # "~25,", } @book{Wilkes:TimeSharing, author = "Maurice Vincent Wilkes", title = "Time-Sharing Computer Systems", publisher = "Elsevier", address = "New York", year = "1968", } @InProceedings{Yianilos:VPTree, author = "Peter N. Yianilos", title = "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces", pages = "311--321", booktitle = "Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms {(SODA'93)}", year = "1993", publisher = "ACM/SIAM", } % ISBN = "0-89871-313-7", % address = "Austin, TX, USA", % month = jan, %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @techreport{Dasgupta:JLL, author = "Sanjoy Dasgupta and Anupam Gupta", title = "An elementary proof of the {J}ohnson-{L}indenstrauss {L}emma", institution = "International Computer Science Institute", number = "TR-99-006", address = "Berkeley, California", year = "1999", url = "http://citeseer.nj.nec.com/dasgupta99elementary.html" } @incollection{DMCA, author = "{U.S. Congress}", title = "{Digital} {Millennium} {Copyright} {Act} ({DMCA})", booktitle = "United States Code, Title 17", type = "section", chapter = "1201", publisher = "U.S. Copyright Office", year = 1998 } @InProceedings{Filho:Similarity, author = "Roberto Filho and Agma Traina and Caetano Traina Jr. and Christos Faloutsos", title = "Similarity Search without Tears: The {OMNI}-Family of All-Purpose Access Methods", pages = "623--632", booktitle = "17th International Conference on Data Engineering ({ICDE} '01)", ISBN = "0-7695-1001-9", month = apr, publisher = "IEEE", year = "2001", } @inproceedings{Fridrich:Visual, author = "Jiri Fridrich", title = "Visual Hash for Oblivious Watermarking", pages = "286--294", booktitle = "SPIE Photonic West Electronic Imaging 2000, Security and Watermarking of Multimedia Contents", month = jan # "~24--26,", year = 2000, address = "San Jose, California", } @misc{GIMP, author = "Peter Mattis and Spencer Kimball", title = "The {GNU} Image Manipulation Program ({GIMP}) 1.2.3", howpublished = "Computer software", note = "Online {\url{http://www.gimp.org/}}", } @book{HarryPotter, author = "{Columbus~(dir.)},Chris", title = "Harry {Potter} and the Philosopher's Stone", publisher = "Warner Home Video", year = "2002", note = "Canadian DVD release of 2001 motion picture from Warner Brothers Pictures.", } @inproceedings{Hjaltason:Ranking, author = "G{\'i}sli R. Hjaltason and Hanan Samet", title = "Ranking in Spatial Databases", booktitle = "Advances in Spatial Databases: Proceedings of the 4th International Symposium on Large Spatial Databases ({SSD} {'95})", pages = "83--95", year = "1995", month = aug, editor = "M. J. Egenhofer and J. R. Herring", number = 951, series = "Lecture Notes in Computer Science", address = "Portland, {ME}, {USA}", publisher = "Springer-Verlag", url = "citeseer.nj.nec.com/hjaltason95ranking.html" } @inproceedings{JohnsonLindenstrauss, author = "Johnson, W.B. and Lindenstrauss, J.", title = "Extensions of {L}ipschitz maps into a {H}ilbert space", booktitle = "Conference in Modern Analysis and Probability (1982, {Y}ale {U}niversity)", pages = "189--206", publisher = "{AMS}", year = 1984, volume = 26, series = "Contemporary Mathematics", uwcallnum = "QA299.6 .C66 1982", } % FIXME @misc{libpng, author = "Greg Roelofs", title = "{\texttt{libpng} 1.0.12}", howpublished = "Computer software", note = "Online {\url{http://www.libpng.org/pub/png/}}", } @book{PerfectBlue, author = "{Kon~(dir.)}, Satoshi", title = "Perfect Blue", publisher = "Manga Entertainment", year = "2000", note = "North American DVD release of 1999 motion picture from Rex Entertainment.", } @book{PrincessBride, author = "{Reiner~(dir.)}, Rob", title = "The Princess Bride (Special Edition)", publisher = "MGM Home Entertainment", year = "2001", note = "North American DVD release of 1987 motion picture from Act III Communications.", } @InProceedings{RKV:Nearest, author = "Nick Roussopoulos and Stephen Kelley and Fr{\'e}d{\'e}ric Vincent", title = "Nearest neighbor queries", editor = "{ACM}", booktitle = "Proceedings of the 1995 {ACM} {SIGMOD} International Conference on Management of Data: May 23--25, 1995, San Jose, California", volume = "24(2)", publisher = "ACM Press", address = "New York, NY 10036, USA", year = "1995", ISBN = "0-89791-731-6", ISSN = "0163-5808", series = "SIGMOD Record (ACM Special Interest Group on Management of Data)", pages = "71--79", year = "1995", bibdate = "Wed Oct 25 08:47:40 MDT 2000", url = "http://www.acm.org/pubs/articles/proceedings/mod/223784/p71-roussopoulos/p71-roussopoulos.pdf; http://www.acm.org/pubs/citations/proceedings/mod/223784/p71-roussopoulos/", } @misc{transcode, author = "Thomas {\"{O}streich (maintainer)}", title = "{\texttt{transcode} 0.6.1}", howpublished = "Computer software", note = "Online {\url{http://www.theorie.physik.uni-goettingen.de/\textasciitilde{}ostreich/transcode/}}", } % " @InProceedings{Yianilos:Excluded, author = "Peter N. Yianilos", title = "Excluded Middle Vantage Point Forests for Nearest Neighbour Search", booktitle = "Algorithm Engineering and Experimentation: International Workshop ({ALENEX} {'99})", address = "Baltimore, MD, USA", year = "1999", month = jan # "~15--16", } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @proceedings{SecurityParallel:2004, booktitle = "2004 International Workshop on Security in Parallel and Distributed Systems", year = 2004, month = sep # "~15--17,", } % address = "San Francisco, {CA}, {USA}",