paper.bib

@String{PODS = "Proc. of ACM Symposium on Principles of Database

          Systems (PODS)"}

@String{DBPL = "Proc. of Int'l Workshop on Database Programming Languages (DBPL)"}

@String{JCSS = {Journal of Computer and System Sciences (JCSS)}}

@String{TKDE = {IEEE Trans. on Data and Knowledge Engineering}}

@String{CACM = {Communicationforeign keyss of the ACM}}

@String{ACMCS = {ACM Computing Surveys}}

@String{JACM = {Journal of the ACM}}

@String{TSE = {IEEE Trans. on Software Engineering}}

@String{TOOIS = "ACM Trans. on Office Information Systems"}

@String{TODS = "ACM Trans. on Database Systems"}

@String{TOPLAS = "ACM Trans. on Programming Languages and Systems"}

@String{VLDB = "Proc. of Int'l Conf. on Very Large Databases (VLDB)"}

@String{ICDT = "Proc. of Int'l Conf. on Database Theory (ICDT)"}

@String{ICDE = "Proc. of IEEE Int'l Conf. on Data Engineering (ICDE)"}

@String{OODBS86 = "Proc. of IEEE Int'l Workshop on Object-Oriented Database Systems"}

@String{SIGMOD = "Proc. of ACM SIGMOD Conf. on Management of Data"}

@String{SIGPLAN = "Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation"}

@String{Wesley = "Addison Wesley, Reading, MA"}

@String{BTW =  "Proceedings der GI-Fachtagung Datenbanksysteme f{\"u}r B{\"u}ro, Technik und Wissenschaft (BTW)"}

@String{DOOD = "Proceedings International Conference on Deductive and Object-Oriented Databases (DOOD)"}

@String{DKEng = "Data \& Knowledge Engineering"}

@String{IJCAI = "International Joint Conference on Artificial Intelligence"}

@String{AAAI = "Proceedings National Conference on Artificial Intelligence"}

@String{DAC= "Proceedings of Design Automation Conference"}

@String{EDBT= "Proceedings of the International Conference on Extending Database Technology"}

@String{HICSS= "Proceedings of the Hawaiian Conference on Computer and System Sciences"}

@String{FOOL = "Proceedings of the Foundations of Object-Oriented Languages Workshop"}

@String{TCS = "Theoretical Computer Science"}

@String{TSI = "Technology and Science of Informatics"}

@String{SEMIWORK = "Workshop on Management of Semistructured Data"}

@String{ACMTOIS = "ACM Transactions on Information Systems"}

@String{DL = "Proceedings of ACM Conference on Digital Libraries"}

@String{COOPIS = {Proceedings of International Conference on Cooperative Information Systems (CoopIS)}}

@String{LNCS = {Lecture Notes in Computer Science}}

@String{WWW = {Proceedings of International {W}orld {W}ide {W}eb Conference}}

@String{RIDE = {Research Issues in Data Engineering}}

@String{NGITS = {Next Generation Information Technologies and

          Systems}}

@String{LICS = {Proceedings of Logic in Computer Science (LICS)}}



@string{siamjc = "{SIAM} Journal on Computing"}

@string{tsmc = "{IEEE} Transactions on Systems, Man, and Cybernetics"}



@INPROCEEDINGS{Han01b,

    AUTHOR={A. Robles-Kelly and E.R.Hancock},

    TITLE={Graph Matching using Adjacency Matrix Markov Chains},

    BOOKTITLE={British Machine Vision Conference},

    YEAR={2001},
}

@inproceedings{DorrigivLS08,
  author    = {Reza Dorrigiv and
               Alejandro L{\'o}pez-Ortiz and
               Alejandro Salinger},
  title     = {Optimal speedup on a low-degree multi-core parallel architecture
               ({LoPRAM})},
  booktitle = {SPAA},
  year      = {2008},
  pages     = {185-187}
  }



@ARTICLE{PEL99,

    AUTHOR={M. Pelillo and K. Siddiqi and S. Zucker},

    TITLE={Matching Hierarchical Structures Using Association Graphs},

    JOURNAL={IEEE Transactions on Pattern Analysis and Machine

          Intelligence},

    VOLUME={21},

    NUMBER={11},

    MONTH={November},

    YEAR={1999},

    PAGES={1105--1120}}



@ARTICLE{gr96,
        AUTHOR={S. Gold and A. Rangarajan},
        title = {A Graduated Assignment Algorithm for Graph
                 Matching},
        JOURNAL={IEEE Transactions on Pattern Analysis and Machine Intelligence},
        VOLUME={18},
        pages = {377--388},
        year = {1996}}


@ARTICLE{hz83,
        AUTHOR={R. Hummel and S. Zucker},
    TITLE={On the foundations of relaxation labeling processes},
    JOURNAL={IEEE PAMI},
    VOLUME={5},
    PAGES={267--287},
    YEAR={1983}}



@ARTICLE{lw66,
        AUTHOR={E. Lawler and D. Wood},
    TITLE={Branch and Bound methods: A survey},
    JOURNAL={Operations Research},
    VOLUME={14},
    PAGES={699--719},
    YEAR={1966}}



@Article{css2003,
  author = {B.  Csaba, A. and Shokoufandeh  and E.  Szemer\'edi},
  title =  {Proof of a Conjecture of Bollobas and Eldridge for
            Graphs of Maximum Degree Three},
  journal = "Combinatorica",
  year = 2003,
  volume = 23,
  pages =  {35-72}
}



@Article{coha63,
  author = {H. Corr\'adi and A. Hajnal},
  title =  {On the Maximal Number of Independent Circuits in a Graph},
  journal = "Acta Math. Hung.",
  year = 1963,
  volume = 14,
  pages =  {423-439}
}





@Article{alfs96,
  author = {N. Alon and E. Fischer},
  title =  {$2$-factors in dense graphs},
  journal = "Discrete Math.",
  year = 1996,
  volume = 152,
  pages =  {13-23}
}



@INCOLLECTION{hasz70,
    AUTHOR={A. Hajnal and E. Szemer\'edi},
    TITLE={Proof of a Conjecture of Erd\"{o}s},
    BOOKTITLE={Combinatorial Theory and Its Applications, II},
    EDITOR={P. Erd\"{o}s and V. T.  S\'os, Eds.},
    PUBLISHER={Colloquia Mathematica Societatis J\'anos Bolyai,
                   North-Holland, Amsterdam/London},
    YEAR={1970}}





@Article{be78,
  author = {B. Bollob\'as and S.E. Eldridge},
  title =  {Packing of Graphs and Applications to Computational Complexity},
  journal = "Journal of Combinatorial Theory, Series B",
  year =  1978,
  volume = 25,
  pages =  {105-124}
}





@Article{KS93,
  author = {J. Koml\'os, M. Simonovits},
  title =  { Regularity Lemma and its Applications in Graphs Theory},
  journal =      {Combinatorics, Paul Erd\"{o}s is eighty},
  year =         1993,
  volume =       2,
  pages =        {295-352}
}



@article{BusyginBP02,
  author    = {Stanislav Busygin and
               Sergiy Butenko and
               Panos M. Pardalos},
  title     = {A Heuristic for the Maximum Independent Set Problem Based
               on Optimization of a Quadratic Over a Sphere.},
  journal   = {J. Comb. Optim.},
  volume    = {6},
  number    = {3},
  year      = {2002},
  pages     = {287-297}
 }



@Misc{busyginsoftware,
 author =        {Stanislav Busygin},
  title =        {{{QUALEX}: {QU}ick {AL}most {EX}act maximum weight clique/independent set solver}},
  howpublished = {{\sl http://www. busygin.dp.ua/npc.html}}
}

@Misc{uwxml,
 author =        {University of Washington},
  title =        {{XML} Repository},
  howpublished = {\\ {\sl http://www.cs.washington.edu/research/xmldatasets}}
}





@TechReport{wadler,
  author =   {Philip Wadler},
  title =    {A Formal Semantics for Patterns in XSL},
  institution =  {Bell Labs},
  year =     2000
}



@manual{xmlschema0,
     organization = "{World Wide Web Consortium (W3C)}",
     title ="{XML} Schema Part 0: Primer ",
     editor = "David C. Fallside",
     year = 2000,
     note = "{\tt http://www.w3.org/TR/xmlschema-0/ }"
}





@book{dotw,
author    = "Serge Abiteboul and Peter Buneman and Dan Suciu",
title     = "Data on the {Web}. From Relations to Semistructured Data and {XML}",
publisher = "Morgan Kaufman",
year      = "2000"
}



@Misc{ThBeMaMe2000,
 author =        {W3C},
  title =        {{XML Schema}},
  howpublished = {W3C Working Draft},
  month =        may,
  year =         2001
}




@Misc{ClDe1999,
 author =    {James Clark and Steve DeRose},
  title =    {{XML Path Language (XPath)}},
  howpublished = {W3C Working Draft},
  month =    nov,
  year =     1999
}






@Book{AbHuVi1995,
  author =   {Serge Abiteboul and Richard Hull and Victor Vianu},
  title =    {Foundations of Databases},
  publisher =    {Addison-Wesley},
  year =     1995
}



@Book{Raghu2000,
  author =   {Raghu Ramakrishnan and Johannes Gehrke},
  title =    {Database Management Systems},
  publisher =    {McGraw-Hill Higher Education},
  year =     2000
}



@inproceedings{pods11-leonid,
 author = {Pablo Barcel\'{o} and  Leonid Libkin and Juan Reutter},
 title = {Querying graph patterns},
 booktitle = {PODS},
 year = {2011}
 }

@inproceedings{pods10-leonid,
 author = {Pablo Barcel\'{o} and  and Carlos A. Hurtado
  and Leonid Libkin and Peter T. Wood},
 title = {Expressive languages for path queries over graph-structured data},
 booktitle = {PODS},
 year = {2010}
 }


@inproceedings{icdt12-leonid,
 author = {Leonid Libkin and Domagoj Vrgoc},
 title = {Regular Path Queries on Graphs with Data},
 booktitle = {ICDT},
 year = {2012}
 }


@Book{HoUl79,
  author =       {John E. Hopcroft and Jeffery D. Ullman},
  title =        {Introduction to Automata Theory, Languages and Computation},
  publisher =    {Addision Wesley},
  year =         1979
}



@Book{Papa1994,
  author =   {Christos H Papadimitriou},
  title =    {Computational Complexity},
  publisher =    {Addison-Wesley},
  year =     1994
}



@book{fol,
author    = "H. B. Enderton",
title     = "A Mathematical Introduction to Logic",
publisher = "Academic Press",
year      = "1972"
}



@Misc{BrPaSp1998,
  author =   {W3C},
  title =    {{Extensible Markup Language ({XML}) 1.0}},
  howpublished = {W3C Recommendation},
  year =     1998,
  month =    feb,
  note =     {\\\oneurl{http://www.w3.org/TR/REC-xml/}}
}





@Book{Ullm1988,
  author =   {Jeffrey D. Ullman},
  title =    {Database and Knowledge Base Systems},
  publisher =    {Computer Science Press},
  year =     1988
}



@Book{GaJo79,
  author =       {Michael Garey and David Johnson},
  title =        {Computers and Intractability: A Guide to the Theory
          of {NP}-Completeness},
  publisher =    {W. H. Freeman and Company},
  year =         1979
}



@Book{LePa81,
  author =       {Harry R. Lewis  and Christos H. Papadimitrious},
  title =        {Elements of the Theory of Computation},
  publisher =    {Prentice-Hall},
  year =         1981
}




@Article{CoKaVa1990,
  author =   {Stavros S. Cosmadakis and Paris C. Kanellakis and Moshe Y. Vardi},
  title =    {Polynomial-Time Implication Problems for Unary Inclusion Dependencies},
  journal =      "JACM",
  year =     1990,
  volume =   37,
  number =   1,
  pages =    {15-46},
  month =    jan
}



@InProceedings{BeMi1999,
  author =   {Catriel Beeri and Tova Milo},
  title =    {Schemas for Integration and Translation of
          Structured and Semi-Structured Data},
  booktitle =    "ICDT",
  year =         1999
}





@Article{Papa1981,
  author =       {Christos H. Papadimitriou},
  title =        {On the Complexity of Integer Programming},
  journal =      {J. {ACM}},
  year =         1981,
  volume =       28,
  number =       4,
  pages =        {765-768}
}



@Article{Lenstra,
  author =       {H. W. Lenstra},
  title =        {Integer Programming in a Fixed Number of Variables},
  journal =      {{Math. Oper. Res.}},
  volume =   8,
  pages =    {538-548},
  year  =        1983
}



@book{sql,
author    = {J. Melton and A. Simon},
title     = {Understanding the New {SQL}: A Complete Guide},
publisher = {Morgan Kaufman},
year      = 1993
}



@book{solvable,
author    = {B. Dreben and W. D. Goldfarb},
title     = {The Decision Problem:
          Solvable Classes of Quantificational Formulas},
publisher = {Addison-Wesley},
year      = 1979
}



@Article{MaRo1975,
  author =   {Y Matiyasevich and J Robinson},
  title =    {Reduction of an arbitrary {Diophantine} equation to
                 one in 13 unknowns},
  journal =      {{Acta Arithmetica}},
  volume =   27,
  pages =    {521-553},
  year  =        1975
}



@InProceedings{Tarskian,
  author =   {David McAllester and Robert Givan and
                   Carl Witty and Dexter Kozen},
  title =    {Tarskian Set Constraints},
  booktitle =    LICS,
  year = 1996
}


@inproceedings{victor-update,
  author =   {Yannis Papakonstantinou and Victor Vianu},
  title =    {Incremental Validation of {XML} Documents},
  booktitle =    {ICDT},
  year =     2003
}



@inproceedings{atg,
  author =   {Michael Benedikt and Chee Yong Chan and
                 Wenfei Fan and Rajeev Rastogi and
                Shihui Zheng and Aoying Zhou},
  title =    {{DTD}-Directed
         Publishing with Attribute Translation Grammars},
  booktitle =    {VLDB},
  year =     2002
}





@book{tree-automata,
author    = "Hubert Comon and Max Dauchet and Remi Gilleron and
             Florent Jacquemard and Denis Ligiez and Sophie Tison
             and Marc Tommasa",
title     = "Tree Automata Techniques and Applications",
publisher = "Online",
year      = 1999
}



@ARTICLE{rm94,
        AUTHOR={A. Rangarajan and E. Mjolsness},
        title = {A Lagrangian Relaxation Network for Graph Matching},
        JOURNAL={IEEE Intl. Conf. on Neural Networks (ICNN)},
        VOLUME={7},
        pages = {4629--4634, IEEE Press},
        year = {1994}}



@ARTICLE{ad93,
        AUTHOR={H. A. Almohamad and S.O. Duffuaa},
    TITLE={A Linear Programming Approach for the Weighted Graph
                  Matching Problem},
    JOURNAL={IEEE Trans. Patt. Anal. Mach. Intell.},
    VOLUME={15},
    PAGES={522--525},
    YEAR={1993}}



@ARTICLE{um88,
        AUTHOR={S. Umeyama},
    TITLE={An Eigendecomposition Approach to Weighted Graph
                  Matching Problems},
    JOURNAL={IEEE Trans. Patt. Anal. Mach. Intell.},
    VOLUME={10},
    PAGES={695--703},
    YEAR={1988}}



@inproceedings{integration-survey1,
  author =   {Maurizio Lenzerini},
  title =    {Data Integration: A Theoretical Perspective},
  booktitle =    {PODS},
  year =     2002
}

@ARTICLE{views-survey,
    author = {Alon Y. Halevy},
    title = {Answering queries using views: A survey},
    journal = {VLDB J.},
    year = {2001},
    volume = {10},
    number = {4},
    pages = {270-294}
}

@article{regular-path,
  author    = {Diego Calvanese
  and Giuseppe De Giacomo and Maurizio Lenzerini and Moshe Y. Vardi},
  title     = {Rewriting of Regular Expressions and Regular Path Queries},
  journal   = {JCSS},
  volume    = {64},
  number    = {3},
  pages = {443-465},
  year      = {2002}
}


@article{integration-survey2,
    author =     {Erhard Rahm and Philip A. Bernstein},
  title={A survey of approaches to automatic schema matching},
  journal={{VLDB Journal}},
  year={2001}
}

@Article{agsurvey,
 author =        {Alexandru Mateescu and Arto Salomaa},
  title =        {Aspects of classical language theory},
  journal = {{Handbook of Formal Languages, vol. 1}},
  year =         1997
}

@book{Hopcroft69,
 author = {Hopcroft, John E. and Ullman, Jeffrey D.},
 title = {Formal languages and their relation to automata},
 year = {1969},
 publisher = {Addison-Wesley Longman Publishing Co., Inc.}
}




@Article{AGs,
  author =   {P. Deransart and M. {Jourdan (eds)}},
  title =    {{Attribute Grammars and their Applications}},
  journal =      {LNCS 461},
  publisher = {{Spinger-Verlag}},
  year  =        1990
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



@inproceedings{HoS91:pdis,
author    = {W. Hong and M. Stonebraker},
title     = "{Optimization of Parallel Query Execution Plans in XPRS}",
booktitle = "PDIS",
year      = {1991},
pages     = {218-225},
address = "Miami Beach, Florida",
month = "December"
}



@article{Kos00:csur,
author = "D. Kossman",
title = "{The State of the Art in Distributed Query Processing}",
journal = "ACM Computing Surveys",
month = "Dec",
volume =  32,
number = 4,
pages = {422-469},
year = "2000" }







@article{KoS00:tods,
author = "D. Kossman and K. Stocker",
title = "{Iterative Dynamic Programming: A New Class of Query Optimization Algorithms}",
journal = "TODS",
month = "March",
volume =  25,
number = 1,
pages = {43-82},
year = "2000" }





@inproceedings{WFA95:sigmod,
author    = {A.N. Wilschut and J. Flokstra and P.M.G. Apers},
title     = "{Parallel Evaluation of Multi-Join Queries}",
booktitle = "SIGMOD",
year      = {1995}
}





@inproceedings{CaL86:sigmod,
author    = {M.J. Carey and H. Lu},
title     = "{Load Balancing in a Locally Distributed Database System}",
booktitle = "SIGMOD",
year      = {1986}
}





@inproceedings{DSD95:sigmod,
author    = {W. Du and M.-C. Shan and U. Dayal},
title     = "{Reducing Multidatabase Query Response Time by Tree Balancing}",
booktitle = "SIGMOD",
year      = {1995}
}






@InProceedings{hector02,
author= {Sergey Melnik and Hector Garcia-Molina and Erhard Rahm},
title={Similarity Flooding: A Versatile Graph Matching Algorithm},
booktitle="ICDE",
year= 2002
}




@InProceedings{flexibleGQ,
author= {Federica Mandreoli and Riccardo Martoglia and Wilma Penzo},
title={Flexible Query Answering on Graph-modeled Data},
booktitle="EDBT",
year= 2000
}


@InProceedings{mitra00,
author= {Prasenjit Mitra and Gio Wiederhold and Martin L. Kersten},
title={A Graph-Oriented Model for Articulation of Ontology Interdependencies},
booktitle="EDBT",
year= 2000
}








@InProceedings{bernstein03-2,
  author =   {Rachel Pottinger and Philip A. Bernstein},
  title =    {Merging Models Based on Given Correspondences},
  booktitle =    "VLDB",
  year =     2003
}



@InProceedings{Skat,
author= {Prasenjit Mitra and Gio Wiederhold and Martin L. Kersten},
title={A Graph-Oriented Model for Articulation of Ontology Interdependencies},
booktitle="EDBT",
year= 2000
}



@ARTICLE{ab93,
    AUTHOR={M. Aigner and S. Brandt},
    TITLE={Embedding arbitrary graphs of maximum degree two},
    JOURNAL={J. London Math. Soc.,},
    VOLUME={48},
    YEAR={1993},
    PAGES={39-51}}



@ARTICLE{Gabow91,
    AUTHOR={H. N. Gabow and R. E. Tarjan},
    TITLE={Faster Scaling Algorithms for General Graph-Matching
Problems},
    JOURNAL={JACM },
    VOLUME={38},
    NUMBER={4},
    YEAR={1991},
    PAGES={815-853}}





@ARTICLE{Fredman87,
    AUTHOR={M. L. Fredman and R. E. Tarjan},
    TITLE={Fibonacci heaps and their uses in improved network
    optimization algorithms},
    JOURNAL={JACM},
    VOLUME={34},
    YEAR={1987},
    PAGES={596-615}}



@article{zss:ipl92,
author = {Zhang, Kaizhong and Statman, Rick
          and Shasha, Dennis},
title = {{On the editing distance between unordered
          labeled trees}},
journal = ipl,
year = 1992,
month = may,
volume = 42,
pages = {133--139},
}



@article{km:siamjc95,
author = {Kilpel{\" a}inen, Pekka and Mannila, Heikki},
title = {{Ordered and Unordered Tree Inclusion}},
journal = siamjc,
year = 1995,
month = apr,
volume = 24,
number = 2,
pages = {340--356}
}


@article{swzs:tsmc94,
author = {Shasha, Dennis and Wang, Jason Tsong Li and
     Zhang, Kaizhong and Shih, Frank Y.},
title = {{Exact and Approximate Algorithms for Unordered
      Tree Matching}},
journal = tsmc,
year = 1994,
month = apr,
volume = 24,
number = 4,
pages = {668--678},
mynotes = {
}}

@book{apostolico-galil:97,
editor = {Apostolico, Alberto and Galil, Zvi},
title = {{Pattern Matching Algorithms}},
year = 1997,
publisher = {Oxford University Press},
mynotes = {
}}

@book{aho-etal:74,
author = {Aho, Alfred V. and Hopcroft, John E. and Ullman, Jeffrey D.},
title = {{The Design and Analysis of Computer Algorithms}},
year = 1974,
publisher = {Addison-Wesley Publishing Company},
mynotes = {
}}

@inproceedings{Maarten,
 author = {Maarten Marx},
 title = {{XPath} with Conditional Axis Relations},
 booktitle = {EDBT},
 year = {2004}
}



@inproceedings{sat,
 author =        {M Benedikt and W Fan and F Geerts},
  title =        {{XPath} satisfiability in the presence of {DTDs}},
  booktitle = "PODS",
  year =         2005
}


@article{subiso76,
 author = {Ullmann, J. R.},
 title = {An Algorithm for Subgraph Isomorphism},
 journal = {JACM},
 volume = {23},
 number = {1},
 year = {1976},
 pages = {31-42}
 }



@Article{even-path,
  author =      {A LaPaugh and Christos  Papadimitriou},
 title =       {The even-path problem for graphs and digraphs},
 journal =     "Networks",
  volume =       14,
  pages = {507-513},
  year = 1984
}


@article{embedding,
 author =       {Wenfei Fan and Philip Bohannon},
  title =        {Information Preserving {XML} Schema Embedding},
  journal =      {TODS},
  volume  =      33,
  number  =      1,
  year =         2008
}

@inproceedings{Joshi03,
 author = {Sachindra {Joshi et al}},
 title = {A bag of paths model for measuring structural similarity in
{Web} documents},
 booktitle = {KDD},
 year = {2003}
}

@inproceedings{Neardup07,
 author = {Gurmeet Singh Manku and Arvind Jain and Anish Das Sarma},
 title = {Detecting near-duplicates for {Web} crawling},
 booktitle = {WWW},
 year = {2007}
}

@inproceedings{AGU03ext,
 author = {Arvind Arasu and Hector Garcia-Molina and Stanford University},
 title = {Extracting structured data from {Web} pages},
 booktitle = {SIGMOD},
 year = {2003}
}

@article{DH99,
 author = {Jeffrey Dean and Monika R. Henzinger},
 title = {Finding related pages in the {World Wide Web}},
 journal = {Comput. Netw.},
 volume = {31},
 number = {11-16},
 year = {1999}
}

@INPROCEEDINGS{Melnik02,
    author = {Sergey Melnik and Hector Garcia-molina and Erhard Rahm},
    title = {Similarity flooding: A versatile graph matching algorithm},
    booktitle = {ICDE},
    year = {2002}
}

@INPROCEEDINGS{Dehmer_applicationof,
    author = {Matthias Dehmer and Frank Emmert Streib and Er Mehler and J??rgen Kilian and Max M??hlh??user},
    title = {Application of a similarity measure for graphs to
  {Web}-based document structures},
    booktitle = {International Conference on Data Analysis ICA},
    year = {2005}
}

@article{repliweb,
 author = {Junghoo Cho and Narayanan Shivakumar and Hector Garcia-Molina},
 title = {Finding replicated {Web} collections},
 journal = {SIGMOD Rec.},
 volume = {29},
 number = {2},
 year = {2000}
}

@article{syntacweb,
 author = {Andrei Z. Broder and Steven C. Glassman and Mark S. Manasse and Geoffrey Zweig},
 title = {Syntactic clustering of the {Web}},
 journal = {Comput. Netw. ISDN Syst.},
 volume = {29},
 number = {8-13},
 year = {1997}
}

@article{Authos99,
 author = {Jon M. Kleinberg},
 title = {Authoritative sources in a hyperlinked environment},
 journal = {J. ACM},
 volume = {46},
 number = {5},
 year = {1999}
}

@inproceedings{tra99,
 author = {Ravi Kumar and Prabhakar Raghavan and Sridhar Rajagopalan and Andrew Tomkins},
 title = {Trawling the {Web} for emerging cyber-communities},
 booktitle = {WWW},
 year = {1999}
}

@inproceedings{PP97,
 author = {James Pitkow and Peter Pirolli},
 title = {Life, death, and lawfulness on the electronic frontier},
 booktitle = {CHI},
 year = {1997}
}


@misc{BP99,
author    = {Sergey Brin and Lawrence Page},
title     = {Google Search Engine},
doi = {http://doi.acm.org/10.1145/258549.258805},
year = {2000}
}

@INPROCEEDINGS{Perkowitz98,
    author = {Mike Perkowitz and Oren Etzioni},
    title = {Adaptive {Web} sites: Automatically synthesizing {Web} pages},
    booktitle = {Proc.~of Nat'l Conf.~on Artificial Intelligence},
    year = {1998}
}

@inproceedings{Nara96,
 author = {Narayanan Shivakumar and Hector Garcia-Molina},
 title = {Building a scalable and accurate copy detection mechanism},
 booktitle = {DL},
 year = {1996}
}

@Misc{SimilarChecker,
  author =   {Webconfs},
  title =    {Similar page checker},
  note = {www.webconfs.com/similar-page-checker.php}
}

@Misc{SimPack,
  title =    {SimPack Project Page},
  note = {http://www.ifi.uzh.ch/ddis/simpack.html}
}

@Misc{cdk,
  title =    {Chemistry Development Kit (CDK)},
  note = {http://sourceforge.net/projects/cdk/}
}

@Misc{webBase,
  title =   {Stanford WebBase},
  note = {http://diglib.stanford.edu:8091/testbed/doc2/WebBase}
}
@TECHREPORT{Berkhin02surveyof,
    author = {Pavel Berkhin},
    title = {Survey of clustering data mining techniques},
    institution = {},
    year = {2002}
}

@article{overlap01,
 author = {Kriszti\'{a}n Monostori and Arkady Zaslavsky and Heinz Schmidt},
 title = {Efficiency of data structures for detecting overlaps in digital documents},
 journal = {Aust. Comput. Sci. Commun.},
 volume = {23},
 number = {1},
 year = {2001}
}



@article{Bharat99,
 author = {Krishna Bharat and Andrei Broder},
 title = {Mirror, mirror on the {Web}: a study of host pairs with replicated content},
 journal = {Comput. Netw.},
 volume = {31},
 number = {11-16},
 year = {1999}
}

@article{mirrorcmp00,
 author = {Krishna Bharat and Andrei Broder and Jeffrey Dean and Monika R. Henzinger},
 title = {A comparison of techniques to find mirrored hosts on the {WWW}},
 journal = {J. Am. Soc. Inf. Sci.},
 volume = {51},
 number = {12},
 year = {2000}
}

@inproceedings{Conrad04,
 author = {Jack G. Conrad and Cindy P. Schriber},
 title = {Constructing a text corpus for inexact duplicate detection},
 booktitle = {SIGIR},
 year = {2004}
}

@inproceedings{Graphidx07,
 author = {Peixiang Zhao and Jeffrey Xu Yu and Philip S. Yu},
 title = {Graph indexing: tree + delta \<= graph},
 booktitle = {VLDB},
 year = {2007}

}

@inproceedings{Graphcontain07,
 author = {Chen~Chen and Xifeng~Yan and Philip~Yu and Jiawei~Han and
DongQing~Zhang and Xiaohui Gu},
 title = {Towards graph containment search and indexing},
 booktitle = {VLDB},
 year = {2007}
}

@article{Yan06,
 author = {Xifeng Yan and Feida Zhu and Philip S. Yu and Jiawei Han},
 title = {Feature-based similarity search in graph structures},
 journal = {TODS},
 volume = {31},
 number = {4},
 year = {2006}
}


@inproceedings{icdt99,
 author = {Tova Milo and Dan Suciu},
 title = {Index Structures for Path Expressions},
 booktitle = {ICDT},
 year = {1999}
}


@MISC{fmeasure,
  author    = {Wikipedia},
  Title = {{F-measure}},
  note = {{\sl http://en.wikipedia.org/wiki/F-measure}}
}

@MISC{terrorist,
  Title = {{Terrorist organization network}},
  note = {{\sl http://www.start.umd.edu/gtd}}
}

@inproceedings{Ramanan03,
  author    = {Prakash Ramanan},
  title     = {Covering Indexes for XML Queries: Bisimulation - Simulation
               = Negation},
  booktitle = {VLDB},
  year      = {2003}
}


@inproceedings{AC05,
 author = {Manu Aery and Sharma Chakravarthy},
 title = {{eMailSift}: Email Classification Based on Structure and Content},
 booktitle = {ICDM},
 year = {2005}
 }

@INPROCEEDINGS{Liu06gplag,
    author = {Chao Liu and Chen Chen and Jiawei Han and Philip S. Yu},
    title = {GPLAG: Detection of Software Plagiarism by Program Dependence Graph Analysis},
    booktitle = {SIGKDD},
    year = {2006}
}

@INPROCEEDINGS{PJ04,
     AUTHOR={Pavol Hell and Jaroslav Nesetril},
     TITLE={Graphs and Homomorphisms},
     publisher = {Oxford University Press},
     YEAR={2004}
 }

@article{Hall00,
  author    = {Magn{\'u}s M. Halld{\'o}rsson},
  title     = {Approximations of Weighted Independent Set and Hereditary
               Subset Problems},
  journal   = {J. Graph Algorithms Appl.},
  volume    = {4},
  number    = {1},
  year      = {2000}
}

@ARTICLE{Bunke00,
    author = {Horst Bunke},
    title = {Graph Matching: Theoretical Foundations, Algorithms, and Applications},
    journal = {Vision Interface},
    year = {2000},
    volume = {3}
}

@INPROCEEDINGS{Langberg06,
    author = {Michael Langberg and Yuval Rabani and Chaitanya Swamy},
    title = {Approximation algorithms for graph homomorphism problems},
    booktitle = {APPROX},
    year = {2006}
}

@ARTICLE{Pavol00,
    author = {Pavol Hell},
    title = {Algorithmic aspects of graph homomorphisms},
    journal = {London Math. Society
    Lecture Note Series 307},
    publisher = {Cambridge University Press},
    year = {2003}
}

@inproceedings{Viggo92,
 author = {Viggo Kann},
 title = {On the Approximability of the Maximum Common Subgraph Problem},
 booktitle = {STACS},
 year = {1992}
 }

@inproceedings{Conte03,
  author    = {Donatello Conte and
               C. Guidobaldi and
               Carlo Sansone},
  title     = {A Comparison of Three Maximum Common Subgraph Algorithms
               on a Large Database of Labeled Graphs},
  booktitle = {GbRPR},
  year      = {2003}
}


@inproceedings{Papa08,
  author    = {Panagiotis Papadimitriou 0002 and
               Ali Dasdan and
               Hector Garcia-Molina},
  title     = {{Web} graph similarity for anomaly detection (poster)},
  booktitle = {WWW},
  year      = {2008}
}

@inproceedings{Li05,
 author = {Li Chen and Amarnath Gupta and M. Erdem Kurul},
 title = {Stack-based algorithms for pattern matching on DAGs},
 booktitle = {VLDB},
 year = {2005}
 }

@inproceedings{TianP08,
  author    = {Yuanyuan Tian and
               Jignesh M. Patel},
  title     = {TALE: A Tool for Approximate Large Graph Matching},
  booktitle = {ICDE},
  year      = {2008}
}

@inproceedings{Ziv02,
 author = {Ziv Bar-Yossef and Sridhar Rajagopalan},
 title = {Template detection via data mining and its applications},
 booktitle = {WWW},
 year = {2002},
 publisher = {ACM}
 }

@article{Nuutila94,
  author    = {Esko Nuutila},
  title     = {An Efficient Transitive Closure Algorithm for Cyclic Digraphs},
  journal   = {Inf. Process. Lett.},
  volume    = {52},
  number    = {4},
  year      = {1994}
}

@article{classificaiton,
  author    = {Adam Schenker and Mark Last and Horst Bunke and Abraham Kandel},
  title     = {Classification Of {Web} Documents Using Graph Matching},
  journal   = {IJPRAI},
  volume    = {18},
  number    = {3},
  year      = {2004}
}

@inproceedings{iso1,
 author = {Xifeng Yan and Philip S. Yu and Jiawei Han},
 title = {Substructure Similarity Search in Graph Databases},
 booktitle = {SIGMOD},
 year = {2005}
 }

@inproceedings{DBLP:conf/sigmod/AgrawalBJ89,
  author    = {Rakesh Agrawal and
               Alexander Borgida and
               H. V. Jagadish},
  title     = {Efficient Management of Transitive Relationships in Large
               Data and Knowledge Bases},
  booktitle = {SIGMOD},
  year      = {1989},
}

 @inproceedings{DBLP:conf/sigmod/JinXRW08,
  author    = {Ruoming Jin and
               Yang Xiang and
               Ning Ruan and
               Haixun Wang},
  title     = {Efficiently answering reachability queries on very large
               directed graphs},
  booktitle = {SIGMOD},
  year      = {2008},
}

@article{Bunke97,
  author    = {Horst Bunke},
  title     = {On a relation between graph edit distance and maximum common
               subgraph},
  journal   = {Pattern Recognition Letters},
  volume    = {18},
  number    = {8},
  year      = {1997}
}

@article{ConteFSV04,
  author    = {Donatello Conte and Pasquale Foggia and Carlo Sansone and
           Mario Vento},
  title     = {Thirty Years Of Graph Matching In Pattern Recognition},
  journal   = {IJPRAI},
  volume    = {18},
  number    = {3},
  year      = {2004}
}



@inproceedings{HuangL06,
  author    = {Xiuzhen Huang and
               Jing Lai},
  title     = {Maximum Common Subgraph: Upper Bound and Lower Bound Results},
  booktitle = {IMSCCS (1)},
  year      = {2006},
  pages     = {40-47}
}

@article{ESonbatyI98,
  author    = {Yasser El-Sonbaty and
               M. A. Ismail},
  title     = {A new algorithm for subgraph optimal isomorphism},
  journal   = {Pattern Recognition},
  volume    = {31},
  number    = {2},
  year      = {1998}
}

@inproceedings{BrancaSD99,
  author    = {Antonella Branca and
               Ettore Stella and
               Arcangelo Distante},
  title     = {Feature Matching by Searching Maximum Clique on High Order
               Association Graph},
  booktitle = {ICIAP},
  year      = {1999}
}

@article{RaymondGW02,
  author    = {John W. Raymond and
               Eleanor J. Gardiner and
               Peter Willett},
  title     = {RASCAL: Calculation of Graph Similarity using Maximum Common
               Edge Subgraphs},
  journal   = {Comput. J.},
  volume    = {45},
  number    = {6},
  year      = {2002}
}

@article{MessmerB98,
  author    = {Bruno T. Messmer and
               Horst Bunke},
  title     = {A New Algorithm for Error-Tolerant Subgraph Isomorphism
               Detection},
  journal   = {IEEE Trans. Pattern Anal. Mach. Intell.},
  volume    = {20},
  number    = {5},
  year      = {1998}
}

@inproceedings{ZasBV08,
  author    = {Mikhail Zaslavskiy and
               Francis Bach and
               Jean-Philippe Vert},
  title     = {A Path Following Algorithm for Graph Matching},
  booktitle = {ICISP},
  year      = {2008}
}

@article{Hagadone92,
  author    = {Thomas R. Hagadone},
  title     = {Molecular substructure similarity searching: efficient retrieval
               in two-dimensional structure databases},
  journal   = {J. Chem. Inf. Comput. Sci.},
  volume    = {32},
  number    = {5},
  year      = {1992}
}

@inproceedings{BKS02,
 author = {Nicolas Bruno and Nick Koudas and Divesh Srivastava},
 title = {Holistic twig joins: optimal {XML} pattern matching},
 booktitle = {SIGMOD},
 year = {2002}
}

@inproceedings{Shasha02,
 author = {Dennis Shasha and Jason T. L. Wang and Rosalba Giugno},
 title = {Algorithmics and applications of tree and graph searching},
 booktitle = {PODS},
 year = {2002}
 }

@book{Aggarwal10,
author    = "Charu C. Aggarwal and Haixun Wang",
title     = "Managing and Mining Graph Data",
publisher = "Springer",
year      = "2010"
}



 @inproceedings{KakoOHH05,
  author    = {Akihisa Kako and
               Takao Ono and
               Tomio Hirata and
               Magn{\'u}s M. Halld{\'o}rsson},
  title     = {Approximation Algorithms for the Weighted Independent Set
               Problem},
  booktitle = {WG},
  year      = {2005}
  }

@Book{approx03,
  author =   {Vijay V. Vazirani},
  title =    {Approximation Algorithms},
  publisher =    "Springer",
  year = 2003
}

@article{BoppanaH92,
  author    = {Ravi B. Boppana and
               Magn{\'u}s M. Halld{\'o}rsson},
  title     = {Approximating Maximum Independent Sets by Excluding Subgraphs},
  journal   = {BIT},
  volume    = {32},
  number    = {2},
  year      = {1992}
}


@Book{Mehlhorn84,
  author =   {Kurt Mehlhorn},
  title =    {Data Structures and Algorithms. Vol. 1-3},
  publisher =    "Springer",
  year = 1984
}

@book{CormenLRS01,
  author    = {Thomas H. Cormen and
               Charles E. Leiserson and
               Ronald L. Rivest and
               Clifford Stein},
  title     = {Introduction to Algorithms},
  publisher = {The MIT Press},
  year      = {2001},
}
@inproceedings{Anthony,
  author    = {Z. Zeng and A. K.H. Tung and J. Wang and J. Feng and L. Zhou},
  title     = {Edit distance evaluation on graph structures},
  booktitle = {VLDB},
  year      = {2009}
  }



@techreport{ilprints836,
          author = {Panagiotis Papadimitriou and Ali Dasdan and Hector Garcia-Molina},
           title = {Web Graph Similarity for Anomaly Detection},
            type = {Technical Report},
       publisher = {Stanford},
            year = {2008},
             url = {http://ilpubs.stanford.edu:8090/836/}
}



@inproceedings{ChengYDYW08,
  author    = {Jiefeng Cheng and
               Jeffrey Xu Yu and
               Bolin Ding and
               Philip S. Yu and
               Haixun Wang},
  title     = {Fast Graph Pattern Matching},
  booktitle = {ICDE},
  year      = {2008}
}

@article{SanzMGB08,
  author    = {Ismael Sanz and
               Marco Mesiti and
               Giovanna Guerrini and
               Rafael Berlanga Llavori},
  title     = {Fragment-based approximate retrieval in highly heterogeneous
               XML collections},
  journal   = {Data Knowl. Eng.},
  volume    = {64},
  number    = {1},
  year      = {2008},
  pages     = {266-293}
}

@article{Blon04,
 author = {Blondel, Vincent D. and Gajardo, Anah\'{\i} and Heymans, Maureen and Senellart, Pierre and Dooren, Paul Van},
 title = {A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching},
 journal = {SIAM Rev.},
 volume = {46},
 number = {4},
 year = {2004},
 pages = {647-666},
 publisher = {Society for Industrial and Applied Mathematics},
 }



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@inproceedings{SokolskyKL06,
  author    = {Oleg Sokolsky and
               Sampath Kannan and
               Insup Lee},
  title     = {Simulation-Based Graph Similarity},
  booktitle = {TACAS},
  year      = {2006},
  pages     = {426-440}
}


@article{DemetrescuI06,
  author    = {Camil Demetrescu and
               Giuseppe F. Italiano},
  title     = {Dynamic shortest paths and transitive closure: Algorithmic
               techniques and data structures},
  journal   = {J. Discrete Algorithms},
  volume    = {4},
  number    = {3},
  year      = {2006},
  pages     = {353-383}
}

@inproceedings{RonenS09-1,
  author    = {Royi Ronen and
               Oded Shmueli},
  title     = {{SoQL}: A Language for Querying and Creating Data in Social
               Networks},
  booktitle = {ICDE},
  year      = {2009},
  pages     = {1595-1602}
}

@article{AmerYahiaBB07,
  author    = {Sihem Amer-Yahia and
               Michael Benedikt and
               Philip Bohannon},
  title     = {Challenges in Searching Online Communities},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {30},
  number    = {2},
  year      = {2007},
  pages     = {23-31}
}



@inproceedings{KRRT99,
  author    = {Jon M. Kleinberg and
               Ravi Kumar and
               Prabhakar Raghavan and
               Sridhar Rajagopalan and
               Andrew Tomkins},
  title     = {The {Web} as a Graph: Measurements, Models, and Methods},
  booktitle = {COCOON},
  year      = {1999}
}

@techreport{ilprints836,
    author  = {Panagiotis Papadimitriou and Ali Dasdan and Hector Garcia-Molina},
    title = {Web Graph Similarity for Anomaly Detection},
        type = {Technical Report},
    publisher = {Stanford},
    year = {2008}
}


@article{AmerYahiaBLS08,
  author    = {Sihem Amer-Yahia and
               Michael Benedikt and
               Laks V. S. Lakshmanan and
               Julia Stoyanovich},
  title     = {Efficient network aware search in collaborative tagging
               sites},
  journal   = {PVLDB},
  volume    = {1},
  number    = {1},
  year      = {2008}
}

@inproceedings{ChengYLWY08,
  author    = {Jiefeng Cheng and
               Jeffrey Xu Yu and
               Xuemin Lin and
               Haixun Wang and
               Philip S. Yu},
  title     = {Fast computing reachability labelings for large graphs with
               high compression rate},
  booktitle = {EDBT},
  year      = {2008}
}

@inproceedings{RaghavanG03,
  author    = {Sriram Raghavan and
               Hector Garcia-Molina},
  title     = {Representing {Web} Graphs},
  booktitle = {ICDE},
  year      = {2003}
}
@inproceedings{BoldiRSV11,
  author    = {Paolo Boldi and
               Marco Rosa and
               Massimo Santini and
               Sebastiano Vigna},
  title     = {Layered label propagation: A multiresolution coordinate-free
               ordering for compressing social networks},
  booktitle = {WWW},
  year      = {2011}
}
@inproceedings{RandallSWW02,
  author    = {Keith H. Randall and
               Raymie Stata and
               Janet L. Wiener and
               Rajiv Wickremesinghe},
  title     = {The Link Database: Fast Access to Graphs of the {Web}},
  booktitle = {DCC},
  year      = {2002}
}

@inproceedings{BuehrerC08,
  author    = {Gregory Buehrer and
               Kumar Chellapilla},
  title     = {A scalable pattern mining approach to {Web} graph compression
               with communities},
  booktitle = {WSDM},
  year      = {2008}
}

@inproceedings{MaserratP10,
  author    = {Hossein Maserrat and
               Jian Pei},
  title     = {Neighbor query friendly compression of social networks},
  booktitle = {KDD},
  year      = {2010}
}

@inproceedings{NavlakhaRS08,
  author    = {Saket Navlakha and
               Rajeev Rastogi and
               Nisheeth Shrivastava},
  title     = {Graph summarization with bounded error},
  booktitle = {SIGMOD},
  year      = {2008}
}

@inproceedings{KaushikSBG02,
  author    = {Raghav Kaushik and
               Pradeep Shenoy and
               Philip Bohannon and
               Ehud Gudes},
  title     = {Exploiting Local Similarity for Indexing Paths in Graph-Structured
               Data},
  booktitle = {ICDE},
  year      = {2002}
}

@article{FederM95,
  author    = {Tom{\'a}s Feder and
               Rajeev Motwani},
  title     = {Clique Partitions, Graph Compression and Speeding-Up Algorithms},
  journal   = {JCSS},
  volume    = {51},
  number    = {2},
  year      = {1995},
  pages     = {261-272}
}

@inproceedings{HeS08,
  author    = {Huahai He and
               Ambuj K. Singh},
  title     = {Graphs-at-a-time: query language and access methods for
               graph databases},
  booktitle = {SIGMOD},
  year      = {2008}
}

@inproceedings{HeymannKG08,
  author    = {Paul Heymann and
               Georgia Koutrika and
               Hector Garcia-Molina},
  title     = {Can social bookmarking improve web search?},
  booktitle = {WSDM},
  year      = {2008}
}

@inproceedings{JinXRW08,
  author    = {Ruoming Jin and
               Yang Xiang and
               Ning Ruan and
               Haixun Wang},
  title     = {Efficiently answering reachability queries on very large
               directed graphs},
  booktitle = {SIGMOD},
  year      = {2008}
}

@article{SarkasDK09,
  author    = {Nikos Sarkas and
               Gautam Das and
               Nick Koudas},
  title     = {Improved Search for Socially Annotated Data},
  journal   = {PVLDB},
  volume    = {2},
  number    = {1},
  year      = {2009}
}

@inproceedings{TianHP08,
  author    = {Yuanyuan Tian and
               Richard A. Hankins and
               Jignesh M. Patel},
  title     = {Efficient aggregation for graph summarization},
  booktitle = {SIGMOD Conference},
  year      = {2008},
  pages     = {567-580}
}

@inproceedings{DBLP:conf/icdt/Wood03,
  author    = {Peter T. Wood},
  title     = {Containment for {XPath} Fragments under {DTD} Constraints},
  booktitle = {ICDT},
  year      = {2003},
}


@inproceedings{DBLP:conf/sigmod/Ramanan02,
  author    = {Prakash Ramanan},
  title     = {Efficient algorithms for minimizing tree pattern queries},
  booktitle = {SIGMOD},
  year      = {2002},
}

@inproceedings{DBLP:conf/sigmod/ChenC08,
  author    = {Ding Chen and
               Chee Yong Chan},
  title     = {Minimization of tree pattern queries with constraints},
  booktitle = {SIGMOD},
  year      = {2008},
}

@inproceedings{TEDI10,
  author    = {Fang Wei},
  title     = {{TEDI}: Efficient Shortest Path Query Answering on Graphs},
  booktitle = {SIGMOD},
  year      = {2010},
}

@inproceedings{WangHYYY06,
  author    = {Haixun Wang and
               Hao He and
               Jun Yang and
               Philip S. Yu and
               Jeffrey Xu Yu},
  title     = {Dual Labeling: Answering Graph Reachability Queries in Constant
               Time},
  booktitle = {ICDE},
  year      = {2006}
}

@inproceedings{XuYFS07,
  author    = {Xiaowei Xu and
               Nurcan Yuruk and
               Zhidan Feng and
               Thomas A. J. Schweiger},
  title     = {SCAN: a structural clustering algorithm for networks},
  booktitle = {KDD},
  year      = {2007}
}


@inproceedings{NeumannW09,
  author    = {Thomas Neumann and
               Gerhard Weikum},
  title     = {Scalable join processing on very large RDF graphs},
  booktitle = {SIGMOD},
  year      = {2009},
  pages     = {627-640}
}

@article{ZhouCY09,
  author    = {Yang Zhou and
               Hong Cheng and
               Jeffrey Xu Yu},
  title     = {Graph Clustering Based on Structural/Attribute Similarities},
  journal   = {PVLDB},
  volume    = {2},
  number    = {1},
  year      = {2009}
}

@article{AmerYahiaRCDY09,
  author    = {Sihem Amer-Yahia and
               Senjuti Basu Roy and
               Ashish Chawla and
               Gautam Das and
               Cong Yu},
  title     = {Group Recommendation: Semantics and Efficiency},
  journal   = {PVLDB},
  volume    = {2},
  number    = {1},
  year      = {2009}
}

@article{CormodeSBK09,
  author    = {Graham Cormode and
               Divesh Srivastava and
               Smriti Bhagat and
               Balachander Krishnamurthy},
  title     = {Class-based graph anonymization for social network data},
  journal   = {PVLDB},
  volume    = {2},
  number    = {1},
  year      = {2009}
}

@article{SarkasDK09,
  author    = {Nikos Sarkas and
               Gautam Das and
               Nick Koudas},
  title     = {Improved Search for Socially Annotated Data},
  journal   = {PVLDB},
  volume    = {2},
  number    = {1},
  year      = {2009}
}


@inproceedings{QinYCT09,
  author    = {Lu Qin and
               Jeffrey Xu Yu and
               Lijun Chang and
               Yufei Tao},
  title     = {Querying Communities in Relational Databases},
  booktitle = {ICDE},
  year      = {2009}
}

@article{AnglesG08,
  author    = {Renzo Angles and
               Claudio Guti{\'e}rrez},
  title     = {Survey of graph database models},
  journal   = {ACM Comput. Surv.},
  volume    = {40},
  number    = {1},
  year      = {2008}
}



@article{NardoRT09,
  author    = {Lorenzo De Nardo and
               Francesco Ranzato and
               Francesco Tapparo},
  title     = {The Subgraph Similarity Problem},
  journal   = {TKDE},
  volume    = {21},
  number    = {5},
  pages = {748-749},
  year      = {2009}
}

@inproceedings{rho,
  author    = {Kemafor Anyanwu and Amit Sheth},
  title     = {{$\rho$-Queries}:
         Enabling querying for semantic associations on the
           semantic {Web}},
  booktitle = {WWW},
  year      = {2003}
}

@inproceedings{edit,
  author    = {Zhiping~Zeng and Anthony Tung
      and Jianyong~Wang and Jianhua~Feng and Lizhu~Zhou},
  title     = {Comparing Stars:~On Approximating Graph Edit Distance},
  booktitle = {VLDB},
  year      = {2009}
}


@article{Cohen,
  author    = {Edith~Cohen and Eran~Halperin and Haim~Kaplan and Uri~Zwick},
  title     = {Reachability and Distance Queries via 2-Hop Labels},
  journal   = {SICOMP},
  volume    = {32},
  number    = {5},
  year      = {2003},
  pages = {1338-1355}
}


@inproceedings{Jin09,
  author    = {Ruoming~Jin and Yang~Xiang and Ning~Ruan and David~Fuhry},
  title     = {3-HOP:~a high-compression indexing~scheme~for~reachability~query},
  booktitle = {SIGMOD},
  year      = {2009}
}



@inproceedings{Tong07,
  author    = {Hanghang Tong and Christos Faloutsos
            and Brian Gallagher and Tina Eliassi-Rad},
  title     = {Fast best-effort pattern matching in large attributed graphs},
  booktitle = {KDD},
  year      = {2007}
}



@Article{AbQuMcWiWi1997,
  author =   {Serge Abiteboul and Dallan Quass and Jason McHugh and Jennifer Widom and Janet L. Wiener},
  title =    {The Lorel query language for semistructured data},
  journal =      {International Journal on Digital Libraries},
  year =     1997,
  volume =   1,
  number =   1,
  pages =    {68-88}
}

@InProceedings{BuDaHiSu1996,
  author =   {Peter Buneman and Susan B. Davidson and Gerd G. Hillebrand and Dan Suciu},
  title =    {A Query Language and Optimization Techniques for Unstructured Data},
  booktitle =    SIGMOD,
  year =     1996,
 }

@InProceedings{MS02,
  author =   {G. Miklau and Dan Suciu},
  title =    {Containment and equivalence for an XPath fragment},
  booktitle = PODS,
  year =     2002,
 }

@InProceedings{ACLS01,
  author =   {Sihem Amer-Yahia and SungRan Cho and Laks V. S. Lakshmanan and Divesh Srivastava},
  title =    {Tree pattern query minimization},
  booktitle = "SIGMOD",
  year =     2001,
 }

@Article{MS04,
  author =   {G. Miklau and Dan Suciu},
  title =    {Containment and equivalence for an XPath fragment},
  journal =  {JACM},
  year =     2004,
  volume =   51,
  number =   1,
  pages =    {2-45}
}


@Article{MeMiMi1997,
  author =   {Alberto O. Mendelzon and Tova Milo},
  title =    {Formal Models of Web Queries},
  journal =      {Inf. Syst.},
  year =     1998,
  volume =   23,
  number =   8,
  pages =    {615-637}
}

@Article{unql,
  author =   {Peter Buneman and Mary F. Fernandez and Dan Suciu},
  title =    {UnQL: A Query Language and Algebra for Semistructured Data Based on Structural Recursion},
  journal =      {VLDB J.},
  year =     2000,
  volume =   9,
  number =   1,
  pages =    {76-110}
}

@article{xmlql,
  author    = {Alin Deutsch and
               Mary F. Fern{\'a}ndez and
               Daniela Florescu and
               Alon Y. Levy and
               Dan Suciu},
  title     = {A Query Language for XML},
  journal   = {Computer Networks},
  volume    = {31},
  number    = {11-16},
  year      = {1999},
  pages     = {1155-1169},
}

@article{lorel,
  author    = {Serge Abiteboul and
               Dallan Quass and
               Jason McHugh and
               Jennifer Widom and
               Janet L. Wiener},
  title     = {The Lorel Query Language for Semistructured Data},
  journal   = {Int. J. on Digital Libraries},
  volume    = {1},
  number    = {1},
  year      = {1997},
  pages     = {68-88},
}

@InProceedings{soQL,
  author =   {Royi Ronen and Oded Shmueli},
  title =    {{SoQL}: A Language for Querying and
    Creating Data in Social Networks},
  booktitle =    {ICDE},
  year =     2009,
 }

@InProceedings{GQ,
  author =   {Huahai He and Ambuj K. Singh},
  title =    {Graphs-at-a-time: query language and access methods for graph databases},
  booktitle =    {SIGMOD},
  year =     2009,
 }


@INPROCEEDINGS{inc-survey,
    AUTHOR = {G. Ramalingam and Thomas W. Reps},
    TITLE = {A Categorized Bibliography on Incremental Computation},
    BOOKTITLE = "POPL",
    YEAR = {1993}   }


@INPROCEEDINGS{b-matching,
    AUTHOR = {Lei Zou and Lei Chen and M. Tamer \"{O}zsu},
    TITLE = {Distance-Join: Pattern Match Query In a Large Graph Database},
    BOOKTITLE = "PVLDB",
    YEAR = {2009}   }

@INPROCEEDINGS{LCR,
    AUTHOR = {Ruoming Jin and Hui Hong and Haixun Wang and Ning Ruan and Yang Xiang},
    TITLE = {Computing Label-Constraint Reachability in Graph Databases},
    BOOKTITLE = "SIGMOD",
    YEAR = {2010}   }





@inproceedings{DovierPP01,
  author    = {Agostino Dovier and
               Carla Piazza and
               Alberto Policriti},
  title     = {A Fast Bisimulation Algorithm},
  booktitle = {CAV},
  year      = {2001},
  pages     = {79-90}
}



@article{AmerYahiaCLS02,
  author    = {Sihem Amer-Yahia and
               SungRan Cho and
               Laks V. S. Lakshmanan and
               Divesh Srivastava},
  title     = {Tree pattern query minimization},
  journal   = {VLDB J.},
  volume    = {11},
  number    = {4},
  year      = {2002},
  pages = {315-331}
}

@inproceedings{BustanG00,
  author    = {Doron Bustan and
               Orna Grumberg},
  title     = {Simulation Based Minimization},
  booktitle = {CADE},
  year      = {2000},
}

@inproceedings{Ambuj08,
 author = {He, Huahai and Singh, Ambuj K.},
 title = {Graphs-at-a-time: query language and access methods for graph databases},
 booktitle = {SIGMOD},
 year = {2008}
 }

@inproceedings{SuciuD,
 author = {Miklau, Gerome and Suciu, Dan},
 title = {Containment and equivalence for an XPath fragment},
 booktitle = {PODS},
 year = {2002}
 }

@inproceedings{FF07,
 author = {Ranzato, Francesco and Tapparo, Francesco},
 title = {A New Efficient Simulation Equivalence Algorithm},
 booktitle = {LICS},
 year = {2007}
 }

@article{Tarjan72,
  author    = {Robert Endre Tarjan},
  title     = {Depth-First Search and Linear Graph Algorithms},
  journal   = {SICOMP},
  volume    = {1},
  number    = {2},
  year      = {1972},
  pages     = {146-160},
}

@article{Natarajan08,
  author    = {Mangai Natarajan},
  title     = {Understanding the structure of a drug trafficking organization: a conversational analysis},
  journal   = {Crime Prevention Studies},
  volume    = {11},
  pages    = {273-298},
  year      = {2000}
}

@article{Bustan03,
 author = {Bustan, Doron and Grumberg, Orna},
 title = {Simulation-based minimization},
 journal = {TOCL},
 volume = {4},
 number = {2},
 year = {2003},
 pages     = {181-206},
 }

@Misc{GTD,
  title =    "Global Terrorism Database",
  note =     {\\ {\tt http://www.start.umd.edu/gtd/}}
}

@inproceedings{Brzo08,
  author    = {Michael J. Brzozowski and
               Tad Hogg and
               G{\'a}bor Szab{\'o}},
  title     = {Friends and foes: ideological social networking},
  booktitle = {CHI},
  year      = {2008}
}

@inproceedings{TanC01,
  author    = {Li Tan and
               Rance Cleaveland},
  title     = {Simulation Revisited},
  booktitle = {TACAS},
  year      = {2001}
}

@article{JiangR93,
  author    = {Tao Jiang and
               Bala Ravikumar},
  title     = {{Minimal NFA Problems are Hard}},
  journal   = {SICOMP},
  volume    = {22},
  number    = {6},
  year      = {1993},
  pages     = {1117-1141}
}

@Misc{SPARQL,
  author =  {SPARQL},
  note = {{\sl http://www.w3.org/TR/rdf-sparql-query/}}
}

@inproceedings{containment,
  author    = {Frank Neven and Thomas Schwentick},
  title     = {{XPath} Containment in the Presence of Disjunction,
 {DTD}s, and Variables},
  booktitle = {ICDT},
  year      = {2003}
}

@INPROCEEDINGS{AKIndex,
    AUTHOR = {Raghav Kauhik and Pradeep Shenoy and Philip Bohannon and Ehud Gudes},
    TITLE = {Exploiting Local Similarity for Indexing Paths in Graph-Structured Data},
    BOOKTITLE = "ICDE",
    YEAR = {2002}   }



@Article{distance1,
  author =  {Edward P. Chan and Heechul Lim},
  title = {Optimization and evaluation of shortest path queries},
  journal = {VLDB J.},
  year = 2007,
  volume = 16,
  number =  3,
  pages =   {343 - 369}
}

@inproceedings{BauerW09,
  author    = {Reinhard Bauer and
               Dorothea Wagner},
  title     = {Batch Dynamic Single-Source Shortest-Path Algorithms: An
               Experimental Study},
  booktitle = {SEA},
  year      = {2009},
  pages     = {51-62}
}

@article{reps96-sssp,
 author = {Ramalingam, G. and Reps, Thomas},
 title = {An incremental algorithm for a generalization of the shortest-path problem},
 journal = {J. Algorithms},
 volume = {21},
 number = {2},
 year = {1996},
 pages = {267--305}
 }



%%%%%%%%%%%%%%%%%%bibs for siggm

@inproceedings{Garg09,
 author = {Garg, Sanchit and Gupta, Trinabh and Carlsson, Niklas and Mahanti, Anirban},
 title = {Evolution of an online social aggregation network: an empirical study},
 booktitle = {IMC},
 year = {2009}
}

@article{Galla06,
  author    = {Brian Gallagher},
  title     = {Matching structure and semantics: A survey on graph-based pattern matching},
  journal   = {AAAI FS.},
  year      = {2006}
}


@article{Reps96,
 author = {Ramalingam, G. and Reps, Thomas},
 title = {On the computational complexity of dynamic graph problems},
 journal = {TCS},
 volume = {158},
 number = {1-2},
 year = {1996}
 }

@inproceedings{BWolf06,
 author = {Berger-Wolf, Tanya Y. and Saia, Jared},
 title = {A framework for analysis of dynamic social networks},
 booktitle = {KDD},
 year = {2006}
 }

@inproceedings{Zhu98,
 author = {Zhuge, Yue and Garcia-Molina, Hector},
 title = {Graph Structured Views and Their Incremental Maintenance},
 booktitle = {ICDE},
 year = {1998}
 }

@inproceedings{Gupta93,
 author = {Gupta, Ashish and Mumick, Inderpal Singh and Subrahmanian, V. S.},
 title = {Maintaining views incrementally},
 booktitle = {SIGMOD},
 year = {1993}
 }

@inproceedings{Thor00,
 author = {Thorup, Mikkel},
 title = {Dynamic Graph Algorithms with Applications},
 booktitle = {SWAT},
 year = {2000}
 }

@article{Lesk07,
 author = {Leskovec, Jure and Kleinberg, Jon and Faloutsos, Christos},
 title = {Graph evolution: Densification and shrinking diameters},
 journal = {TKDD},
 volume = {1},
 number = {1},
 year = {2007},
 pages = {2},
 publisher = {ACM}
 }

@inproceedings{Yi04,
 author = {Yi, Ke and He, Hao and Stanoi, Ioana and Yang, Jun},
 title = {Incremental maintenance of {XML} structural indexes},
 booktitle = {SIGMOD},
 year = {2004}
 }

@inproceedings{Saha07,
  author    = {Diptikalyan Saha},
  title     = {An Incremental Bisimulation Algorithm},
  booktitle = {FSTTCS},
  year      = {2007}
}

@article{David05,
 author = {Terveen, Loren and McDonald, David W.},
 title = {Social matching: A framework and research agenda},
 journal = {ACM Trans. Comput.-Hum. Interact.},
 volume = {12},
 number = {3},
 year = {2005}
 }

@book{Gutin08,
 author = {Bang-Jensen, Jrgen and Gutin, Gregory Z.},
 title = {Digraphs: Theory, Algorithms and Applications},
 year = {2008},
 publisher = {Springer}
}

@inproceedings{JeffXu09,
 author = {Chen, Zaiben and Shen, Heng Tao and Zhou, Xiaofang and Yu, Jeffrey Xu},
 title = {Monitoring path nearest neighbor in road networks},
 booktitle = {SIGMOD},
 year = {2009},
 }

@article{Chan10,
  author    = {Badrish Chandramouli and
               Jonathan Goldstein and
               David Maier},
  title     = {High-Performance Dynamic Pattern Matching over Disordered
               Streams},
  journal   = {PVLDB},
  year      = {2010},
  pages     = {220-231}
}


@inproceedings{ChoG00,
  author    = {Junghoo Cho and
               Hector Garcia-Molina},
  title     = {The Evolution of the {Web} and Implications for an Incremental
               Crawler},
  booktitle = {VLDB},
  year      = {2000}
}


@article{Epp97,
 author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Nissenzweig, Amnon},
 title = {Sparsification---a technique for speeding up dynamic graph algorithms},
 journal = {J. ACM},
 year = {1997},
 pages = {669--696}
 }


@article{Milt94,
 author = {Miltersen, Peter Bro and Subramanian, Sairam and Vitter, Jeffrey Scott and Tamassia, Roberto},
 title = {Complexity models for incremental computation},
 journal = {Theor. Comput. Sci.},
 volume = {130},
 number = {1},
 year = {1994},
 pages = {203-236}
 }

@Article{MLC2001,
  author =       {Miller McPherson and Lynn Smith-Lovin and James M Cook},
  title =        {Birds of a Feather: Homophily in Social Networks},
  journal =      "Annual Review of Sociology",
  year =         2001,
  volume =       27,
  pages =        {415-444}
}

@Misc{Ffeed,
  author =  {Friendfeed},
  note = {{\sl http://friendfeed.com/}}
}

@inproceedings{Pota09,
 author = {Potamias, Michalis and Bonchi, Francesco and Castillo, Carlos and Gionis, Aristides},
 title = {Fast shortest path distance estimation in large networks},
 booktitle = {CIKM},
 year = {2009}
 }

@inproceedings{Das10,
 author = {Das Sarma, Atish and Gollapudi, Sreenivas and Najork, Marc and Panigrahy, Rina},
 title = {A sketch-based distance oracle for web-scale graphs},
 booktitle = {WSDM},
 year = {2010}
 }

@article{Thor05,
 author = {Thorup, Mikkel and Zwick, Uri},
 title = {Approximate distance oracles},
 journal = {J. ACM},
 year = {2005}
 }

@inproceedings{Kumar06,
 author = {Kumar, Ravi and Novak, Jasmine and Tomkins, Andrew},
 title = {Structure and evolution of online social networks},
 booktitle = {KDD},
 year = {2006}
 }

@article{LeeSC01,
  author    = {Chiang Lee and
               Chi-Sheng Shih and
               Yaw-Huei Chen},
  title     = {Optimizing Large Join Queries Using A Graph-Based Approach},
  journal   = {TKDE},
  year      = {2001}
}


@inproceedings{WhiteS03,
  author    = {Scott White and
               Padhraic Smyth},
  title     = {Algorithms for estimating relative importance in networks},
  booktitle = {KDD},
  year      = {2003}
}


@TECHREPORT{Berger02,
    author = {Sacha Berger and François Bry and Sebastian Schaffert},
    title = {Pattern Queries for {XML} and Semistructured Data},
    institution = {Workshop on logic programming},
    year = {2002}
}

@inproceedings{Junghoo04,
 author = {Ntoulas, Alexandros and Cho, Junghoo and Olston, Christopher},
 title = {What's new on the {Web}? {The} evolution of the {Web} from a search engine perspective},
 booktitle = {WWW},
 year = {2004}
 }


@inproceedings{Sawires05,
 author = {Sawires, Arsany and Tatemura, Junichi and Po, Oliver and Agrawal, Divyakant and Candan, K. Sel\c{C}uk},
 title = {Incremental maintenance of path-expression views},
 booktitle = {SIGMOD},
 year = {2005}
 }

@inproceedings{Abite98,
 author = {Abiteboul, Serge and McHugh, Jason and Rys, Michael and Vassalos, Vasilis and Wiener, Janet L.},
 title = {Incremental Maintenance for Materialized Views over Semistructured Data},
 booktitle = {VLDB},
 year = {1998}
 }


@inproceedings{Bram08,
 author = {Bramandia, Ramadhana and Choi, Byron and Ng, Wee Keong},
 title = {On incremental maintenance of 2-hop labeling of graphs},
 booktitle = {WWW},
 year = {2008}
 }


@INPROCEEDINGS{SandeSim,
    author = {Sandeep K. Shukla and Eep K. Shukla and Daniel J. Rosenkrantz and Harry B. Hunt Iii and Richard E. Stearns},
    title = {The Polynomial Time Decidability of Simulation Relations for Finite State Processes: A {HORNSAT} Based Approach},
    booktitle = {DIMACS Ser. Discrete},
    year = {1997}
}



@inproceedings{Sokol94,
 author = {Sokolsky, Oleg and Smolka, Scott A.},
 title = {Incremental Model Checking in the Modal Mu-Calculus},
 booktitle = {CAV},
 year = {1994}
 }

@inproceedings{Wang09,
 author = {Wang, Changliang and Chen, Lei},
 title = {Continuous Subgraph Pattern Search over Graph Streams},
 booktitle = {ICDE},
 year = {2009}
 }

@article{Chen10,
 author = {Chen, Lei and Wang, Changliang},
 title = {Continuous Subgraph Pattern Search over Certain and Uncertain Graph Streams},
 journal = {TKDE},
 volume = {22},
 number = {8},
 year = {2010},
 pages = {1093-1109}
 }

@article{Stotz09,
    author = {Stotz, A. and Nagi, R. and Sudit, M.},
    title = {Incremental graph matching for Situation Awareness},
    journal = {FUSION},
    year = {2009}
}


@INPROCEEDINGS{Cordella01,
    author = {L. P. Cordella and P. Foggia and C. Sansone and M. Vento},
    title = {An improved algorithm for matching large graphs},
    booktitle = {IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition},
    year = {2001}
}

@INPROCEEDINGS{Foggia01,
    author = {P. Foggia and C. Sansone and M. Vento},
    title = {A performance comparison of five algorithms for graph isomorphism},
    booktitle = {IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition},
    year = {2001}
}


@book{view-survey,
author    = {A. Gupta and I. Mumick},
title     = "Materialized Views",
publisher = "MIT Press",
year      = 2000
}

@INPROCEEDINGS{Lischka09,
    author = {J. Lischka and H. Karl},
    title = {A Virtual Network Mapping Algorithm based on Subgraph Isomorphism Detection},
    booktitle = {ACM SIGCOMM Workshop on Virtualized Infastructure Systems and Architectures},
    year = {2009}
}

@article{Przulj06,
 author = {N. Przulj and D. G. Corneil and I. Jurisica},
 title = {Efficient estimation of graphlet frequency distributions in protein-protein interaction networks},
 journal = {Bioinformatics},
 volume =  {22},
 number = {8},
 pages =  {974-980},
 year = {2006}
 }

@article{McKay81,
 author = {B. D. McKay},
 title = {Practical Graph Isomorphism},
 journal = {Congressus Numerantium},
 volume =  30,
 pages =  {45-87},
 year = {1981}
 }

@INPROCEEDINGS{Ohlrich93,
 author = {M. Ohlrich and C. Ebeling and E. Ginting and L. Sather},
 title = {SubGemini: identifying subcircuits using a fast subgraph isomorphism algorithm},
    booktitle = {International Design Automation Conference},
    year = {1993}
 }


@article{chvatal79,
    author = {Chvatal, V.},
    journal = {Mathematics of Operations Research},
    number = {3},
    title = {A Greedy Heuristic for the Set-Covering Problem},
    volume = {4},
    year = {1979}
}

@inproceedings{Tang08,
 author = {Tang, Jie and Zhang, Jing and Yao, Limin and Li, Juanzi and Zhang, Li and Su, Zhong},
 title = {ArnetMiner: extraction and mining of academic social networks},
 booktitle = {KDD},
 year = {2008}
 }


@inproceedings{TangSWY09,
  author    = {Jie Tang and
               Jimeng Sun and
               Chi Wang and
               Zi Yang},
  title     = {Social influence analysis in large-scale networks},
  booktitle = {KDD},
  year      = {2009}
}


%%%%%%%%%%%distributed distance queries

@article{Haldar97,
  author    = {S. Haldar},
  title     = {An `All Pairs Shortest Paths' Distributed Algorithm Using
               2n$^2$ Messages},
  journal   = {J. Algorithms},
  volume    = {24},
  number    = {1},
  year      = {1997},
  pages     = {20-36}}









distributed data/Motivation

@Misc{XLink,
 author =        {Steven J. DeRose},
  title =        {{XML} Link},
  howpublished = {\\ {\sl http://www.w3.org/TR/NOTE-xlink-req/}}
}



distriputed (graph) pattern matching/query evaluation


@inproceedings{QuilitzL08,
  author    = {Bastian Quilitz and
               Ulf Leser},
  title     = {Querying Distributed {RDF} Data Sources with {SPARQL}},
  booktitle = {ESWC},
  year      = {2008},
  pages     = {524-538},
  ee        = {http://dx.doi.org/10.1007/978-3-540-68234-9_39}}


@inproceedings{NevenC06,
  author    = {Frank Neven and
               Dieter Van de Craen},
  title     = {Optimizing Monitoring Queries over Distributed Data},
  booktitle = {EDBT},
  year      = {2006},
  pages     = {829-846}}
  
  
@inproceedings{GuptaHR00,
  author    = {Nalin Gupta and
               Jayant R. Haritsa and
               Maya Ramanath},
  title     = {Distributed Query Processing on the Web},
  booktitle = {ICDE},
  year      = {2000},
  pages     = {84}}


  
@article{Suciu02,
  author    = {Dan Suciu},
  title     = {Distributed query evaluation on semistructured data},
  journal   = {TODS},
  volume    = {27},
  number    = {1},
  year      = {2002},
  pages     = {1-62}}


@article{Kossmann00,
  author    = {Donald Kossmann},
  title     = {The State of the art in distributed query processing},
  journal   = {ACM Comput. Surv.},
  volume    = {32},
  number    = {4},
  year      = {2000},
  pages     = {422-469}}


@inproceedings{PapadimosM02,
  author    = {Vassilis Papadimos and
               David Maier},
  title     = {Distributed queries without distributed state},
  booktitle = {WebDB},
  year      = {2002},
  pages     = {95-100}}

@article{ShoaranT09,
  author    = {Maryam Shoaran and
               Alex Thomo},
  title     = {Fault-tolerant computation of distributed regular path queries},
  journal   = {TCS},
  volume    = {410},
  number    = {1},
  year      = {2009},
  pages     = {62-77}}


@article{Mohsen10,
  author    = {Mohsen Jamali},
  title     = {A Distributed Method for Trust-Aware Recommendation in Social
               Networks},
  journal   = {CoRR},
  year      = {2010}}


partial evaluation

@article{Jones96,
  author    = {Neil D. Jones},
  title     = {An Introduction to Partial Evaluation},
  journal   = {ACM Comput. Surv.},
  volume    = {28},
  number    = {3},
  year      = {1996},
  pages     = {480-503}
}

@inproceedings{Flesca08,
 author = {Flesca, Sergio and Furfaro, Filippo and Pugliese, Andrea},
 title = {A Framework for the Partial Evaluation of {SPARQL} Queries},
 booktitle = {SUM},
 year = {2008}
}

@inproceedings{StefanescuTT05,
  author    = {Dan C. Stefanescu and
               Alex Thomo and
               Lida Thomo},
  title     = {Distributed evaluation of generalized path queries},
  booktitle = {SAC},
  year      = {2005},
  pages     = {610-616}}




other applications and techniques. Motivation. 


@inproceedings{KumarNT06,
  author    = {Ravi Kumar and
               Jasmine Novak and
               Andrew Tomkins},
  title     = {Structure and evolution of online social networks},
  booktitle = {KDD},
  year      = {2006}
}


@INPROCEEDINGS{Rowe09,
    author = {Matthew Rowe and Oak Group},
    title = {Interlinking distributed social graphs},
    booktitle = {WWW},
    year = {2009}
}


@inproceedings{MisloveMGDB07,
  author    = {Alan Mislove and
               Massimiliano Marcon and
               P. Krishna Gummadi and
               Peter Druschel and
               Bobby Bhattacharjee},
  title     = {Measurement and analysis of online social networks},
  booktitle = {Internet Measurement Comference},
  year      = {2007}}


@inproceedings{HusainDKT09,
  author    = {Mohammad Farhan Husain and
               Pankil Doshi and
               Latifur Khan and
               Bhavani M. Thuraisingham},
  title     = {Storage and Retrieval of Large {RDF} Graph Using Hadoop and
               {MapReduce}},
  booktitle = {CloudCom},
  year      = {2009}
}


@article{MiloD08,
  author    = {Tova Milo and
               Daniel Deutch},
  title     = {Querying and monitoring distributed business processes},
  journal   = {PVLDB},
  volume    = {1},
  number    = {2},
  year      = {2008},
  pages     = {1512-1515}}

@article{DeanG08,
  author    = {Jeffrey Dean and
               Sanjay Ghemawat},
  title     = {{MapReduce}: Simplified data processing on large clusters},
  journal   = {Commun. ACM},
  volume    = {51},
  number    = {1},
  year      = {2008}
}

@inproceedings{StefanescuT06,
  author    = {Dan C. Stefanescu and
               Alex Thomo},
  title     = {Enhanced Regular Path Queries on Semistructured Databases},
  booktitle = {EDBT Workshops},
  year      = {2006},
  pages     = {700-711}}


On simulation related

@ARTICLE{Gentilini03,
    author = {R. Gentilini and C. Piazza and A. Policriti},
    title = {From bisimulation to simulation: coarsest partition problems},
  journal   = {J. Autom. Reasoning},
  volume    = {31},
  number    = {1},
  year      = {2003},
  pages     = {73-103},}
  
@inproceedings{infsimu95,
 author = {M. R. Henzinger and T. Henzinger and P. Kopke},
 title = {Computing simulations on finite and infinite graphs},
 booktitle = {FOCS},
 year = {1995}
}

@inproceedings{brynie10,
    author = {Brynielsson, Joel and H\"{o}gberg, Johanna and Kaati, Lisa and
Martenson, Christian and Svenson, Pontus},
    booktitle = {ASONAM},
    title = {Detecting Social Positions Using Simulation},
    year = {2010}
}

@inproceedings{Nara02,
 author = {Narayanan, Srini and McIlraith, Sheila A.},
 title = {Simulation, verification and automated composition of web services},
 booktitle = {WWW},
 year = {2002}
 }

@article{BerardiCGP08,
  author    = {Daniela Berardi and
               Fahima Cheikh and
               Giuseppe De Giacomo and
               Fabio Patrizi},
  title     = {Automatic Service Composition via Simulation},
  journal   = {Int. J. Found. Comput. Sci.},
  volume    = {19},
  number    = {2},
  year      = {2008},
  pages     = {429-451}}
  
  
@INCOLLECTION{Jef10,
    AUTHOR={Jeffrey Xu Yu and Jiefeng Cheng},
    TITLE={Graph Reachability Queries: A Survey},
    BOOKTITLE={Managing and Mining Graph Data},
    PUBLISHER={Springer},
    YEAR={2010}}



@article{MendelzonW95,
  author    = {Alberto O. Mendelzon and
               Peter T. Wood},
  title     = {Finding Regular Simple Paths in Graph Databases},
  journal   = {SICOMP},
  volume    = {24},
  number    = {6},
  pages = {1235-1258},
  year      = {1995}}
  
  @Misc{facebook,
 author =        {},
  title =        {Facebook Statistics},
  howpublished = {\\ {\sl http://www.facebook.com/press/info.php?statistics}}
}

  @Misc{linkedin,
 author =        {},
  title =        {LinkedIn},
  howpublished = {\\ {\sl http://www.linkedin.com/}}
}


@inproceedings{Yao05,
author = {Andy Yoo and Edmond Chow and Keith Henderson and William McLendon and Bruce Hendrickson and Umit Catalyurek},
title = {A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L},
booktitle  ={SC},
year = {2005}
}


@inproceedings{RaeSZ10,
  author    = {Adam Rae and
               B{\"o}rkur Sigurbj{\"o}rnsson and
               Roelof van Zwol},
  title     = {Improving tag recommendation using social networks},
  year      = {2010},
  pages     = {92-99}}
  
  
  @article{HuntRS76,
  author    = {Harry B. Hunt III and
               Daniel J. Rosenkrantz and
               Thomas G. Szymanski},
  title     = {On the Equivalence, Containment, and Covering Problems for
               the Regular and Context-Free Languages},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {12},
  number    = {2},
  year      = {1976},
  pages     = {222-268}}
  

@inproceedings{QunLO03,
  author    = {Chen Qun and
               Andrew Lim and
               Kian Win Ong},
  title     = {D(k)-Index: An Adaptive Structural Summary for Graph-Structured
               Data},
  booktitle = {SIGMOD},
  year      = {2003}
}  


@inproceedings{Zwick01,
  author    = {Uri Zwick},
  title     = {Exact and Approximate Distances in Graphs - A Survey},
  booktitle = {ESA},
  year      = {2001}
}
  
  
@inproceedings{MiloS99,
  author    = {Tova Milo and
               Dan Suciu},
  title     = {Index Structures for Path Expressions},
  booktitle = {ICDT},
  year      = {1999}
}


@inproceedings{MalewiczABDHLC10,
  author    = {Grzegorz Malewicz and
               Matthew H. Austern and
               Aart J. C. Bik and
               James C. Dehnert and
               Ilan Horn and
               Naty Leiser and
               Grzegorz Czajkowski},
  title     = {Pregel: a system for large-scale graph processing},
  booktitle = {SIGMOD},
  year      = {2010}
}
  
  
  @inproceedings{DiMiccoMGDBM08,
  author    = {Joan Morris DiMicco and
               David R. Millen and
               Werner Geyer and
               Casey Dugan and
               Beth Brownholtz and
               Michael J. Muller},
  title     = {Motivations for social networking at work},
  booktitle = {CSCW},
  year      = {2008},
  pages     = {711-720}}
  
  
  @article{AspvallPT79,
  author    = {Bengt Aspvall and
               Michael F. Plass and
               Robert Endre Tarjan},
  title     = {A Linear-Time Algorithm for Testing the Truth of Certain
               Quantified Boolean Formulas},
  journal   = {Inf. Process. Lett.},
  volume    = {8},
  number    = {3},
  year      = {1979},
  pages     = {121-123}}
  
  
  @inproceedings{Antoshenkov95,
 author = {Antoshenkov, G.},
 title = {Byte-aligned bitmap compression},
 booktitle = {DCC},
 year = {1995},
 } 
 
 
 
 
 
 added related work
 
 
 
 @article{CooperRSSBJPWY08,
  author    = {Brian F. Cooper and
               Raghu Ramakrishnan and
               Utkarsh Srivastava and
               Adam Silberstein and
               Philip Bohannon and
               Hans-Arno Jacobsen and
               Nick Puz and
               Daniel Weaver and
               Ramana Yerneni},
  title     = {PNUTS: Yahoo!'s hosted data serving platform},
  journal   = {PVLDB},
  volume    = {1},
  number    = {2},
  year      = {2008}}
  
  
  @inproceedings{DeCandiaHJKLPSVV07,
  author    = {Giuseppe DeCandia and
               Deniz Hastorun and
               Madan Jampani and
               Gunavardhan Kakulapati and
               Avinash Lakshman and
               Alex Pilchin and
               Swaminathan Sivasubramanian and
               Peter Vosshall and
               Werner Vogels},
  title     = {Dynamo: Amazon's highly available key-value store},
  booktitle = {SOSP},
  year      = {2007}
}
  
  
  
    @Misc{flockdb,
 author =        {},
  title =        {FlockDB},
  howpublished = {{\sl http://engineering.twitter.com/2010/05/introducing-}
 {\sl flockdb.html}}
}

    @Misc{twitter,
 author =        {},
  title =        {Twitter},
  howpublished = {{\sl http://twitter.com/}}
}
  
      @Misc{neo4j,
 author =        {},
  title =        {Neo4J Project},
  howpublished = {{\sl http://neo4j.org/}}
}

      @Misc{hypergraph,
 author =        {},
  title =        {HyperGraphDB Project},
  howpublished = {{\sl http://www.kobrix.com/hgdb.jsp}}
}


      @Misc{trinity,
 author =        {},
  title =        {Trinity},
  howpublished = {\\ {\sl http://research.microsoft.com/en-us/projects/trinity/}}
}


@inproceedings{RonenS09,
  author    = {Royi Ronen and
               Oded Shmueli},
  title     = {Evaluating very large datalog queries on social networks},
  booktitle = {EDBT},
  year      = {2009}
}

@inproceedings{AbbassiL09,
  author    = {Zeinab Abbassi and
               Laks V. S. Lakshmanan},
  title     = {On Efficient Recommendations for Online Exchange Markets},
  booktitle = {ICDE},
  year      = {2009}
}


@article{Pujol09,
  author    = {Josep M. Pujol and
               Vijay Erramilli and
               Pablo Rodriguez},
  title     = {Divide and Conquer: Partitioning Online Social Networks},
  journal   = {CoRR},
  year      = {2009}
}

@article{Greenberg08,
 author = {Greenberg, Albert and Hamilton, James and Maltz, David A. and Patel, Parveen},
 title = {The cost of a cloud: research problems in data center networks},
 journal = {SIGCOMM Comput. Commun. Rev.},
 volume = {39},
 issue = {1},
 year = {2008}
} 


@book{ozsu99,
    author = {Ozsu, M. Tamer and Valduriez, Patrick},
    publisher = {Prentice Hall},
    title = {Principles of Distributed Database Systems},
    year = {1999}
}


@article{ChangDGHWBCFG08,
  author    = {Fay {Chang et al}},
  title     = {Bigtable: A Distributed Storage System for Structured Data},
  journal   = {ACM Trans. Comput. Syst.},
  volume    = {26},
  number    = {2},
  year      = {2008}}
  
  
    @inproceedings{AnhK07,
  author    = {Vu Le Anh and
               Attila Kiss},
  title     = {Efficient Processing Regular Queries In Shared-Nothing Parallel
               Database Systems Using Tree- And Structural Indexes},
  booktitle = {ADBIS Research Communic},
  year      = {2007}}
  
  
    @book{Abiteboul1999,
    address = {San Francisco, CA},
    author = {Abiteboul, Serge and Buneman, Peter and Suciu, Dan},
    publisher = {Morgan Kaufmann Publishers Inc.},
    title = {{Data on the Web: From Relations to Semistructured Data and XML}},
    year = {1999}
}


@inproceedings{GrooteK05,
  author    = {Jan Friso Groote and
               Misa Kein{\"a}nen},
  title     = {A Sub-quadratic Algorithm for Conjunctive and Disjunctive
               Boolean Equation Systems},
  booktitle = {ICTAC},
  year      = {2005},
  pages     = {532-545}}

@article{Tarjin,
  author    = {R Tarjan},
  title     = {Depth-first search and linear graph algorithm},
  journal   = {SICOMP},
  volume    = {1},
  number    = {2},
  year      = {1972}}
  
  
  @article{HromkovicSW01,
  author    = {Juraj Hromkovic and
               Sebastian Seibert and
               Thomas Wilke},
  title     = {Translating Regular Expressions into Small -Free Nondeterministic
               Finite Automata},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {62},
  number    = {4},
  year      = {2001},
  pages     = {565-588}}
  
  
  
  @book{Hopcroft,
 author = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
 title = {Introduction to Automata Theory, Languages, and Computation (3rd Edition)},
 year = {2006},
 isbn = {0321455363},
 publisher = {Addison-Wesley Longman Publishing Co., Inc.}
} 

@inproceedings{AfratiBCPU11,
  author    = {Foto N. Afrati and
               Vinayak R. Borkar and
               Michael J. Carey and
               Neoklis Polyzotis and
               Jeffrey D. Ullman},
  title     = {Map-reduce extensions and recursive queries},
  booktitle = {EDBT},
  year      = {2011}
}
  
  
  @article{Even99,
 author = {Even, Guy},
 title = {Fast Approximate Graph Partitioning Algorithms},
 journal = {SIAM J. Comput.},
 volume = {28},
 issue = {6},
 month = {August},
 year = {1999},
 numpages = {28}} 
 
 
 @inproceedings{AfratiU10,
  author    = {Foto N. Afrati and
               Jeffrey D. Ullman},
  title     = {Optimizing joins in a map-reduce environment},
  booktitle = {EDBT},
  year      = {2010}
}
  
  
  
@article{EvenNRS99b,
  author    = {Per-Olof Fj{\"a}llstr{\"o}m },
  title     = {Algorithms for Graph Partitioning: A Survey},
  journal   = {Linkoping Electronic Articles in Computer and Information Science},
  volume    = {3},
  year      = {1998}
} 


@inproceedings{ChenWHY10,
  author    = {Rishan Chen and
               Xuetian Weng and
               Bingsheng He and
               Mao Yang},
  title     = {Large graph processing in the cloud},
  booktitle = {SIGMOD},
  year      = {2010}}
  
        @Misc{amazonec2,
 author =        {},
  title =        {Amazon {EC2}}, 
  howpublished = {{\sl  http://aws.amazon.com/ec2/}}
}
 
          @Misc{Youtube,
 author =        {},
  title =        {Youtube dataset},
  howpublished = {{\sl  http://netsg.cs.sfu.ca/youtubedata/}}
}
  
             @Misc{citation,
 author =        {},
  title =        {Citation},
  howpublished = {{\sl  http://www.arnetminer.org/citation/}}
}
 
           @Misc{caida,
 author =        {},
  title =        {Caida data},
  howpublished = {{\sl  http://www.caida.org/data/}}
}
 
           @Misc{webgraph,
 author =        {},
  title =        {Webgraph data},
  howpublished = {\\ {\sl  http://law.dsi.unimi.it/datasets.php}}
}

	  @Misc{stanford,

 author =        {},
  title =        {Stanford Large Network Dataset Collection},
  howpublished = {\\ {\sl http://snap.\ stanford.edu/\ data/\ index.html}}

}

 @Misc{mapBFS,

 author =        {Mark Sevalnev},
  title =        {From prefix computation on PRAM for finding Euler tours to usage of Hadoop-framework for distributed breadth first search},
  howpublished = { {\sl http://www.cs.hut.fi/}}

}


@book{graph-book,
author    = "Pavol Hell and Jaroslav Nesetril",
title     = "Graphs and Homomorphisms",
publisher = "Oxford University Press",
year      = "2004"
}

@article{homeo,
  author    = {Steven Fortune and John E. Hopcroft and James Wyllie},
  title     = {The Directed Subgraph Homeomorphism Problem},
  journal   = {TCS},
  volume    = {10},
  pages = {111-121},
  year      = {1980}
} 

%%%%%%%%%%%%%%%%%
@book{ccs,
author    = "Robin Milner",
title     = "Communication and Concurrency",
publisher = "Prentice Hall",
year      = "1989"
}

@article{Ullmann76,
  author    = {Julian R. Ullmann},
  title     = {An Algorithm for Subgraph Isomorphism},
  journal   = {J. ACM},
  volume    = {23},
  number    = {1},
  year      = {1976},
  pages     = {31-42}
}


%%%%%%%%%%%%%%%%% Graph Compression %%%%%%%%%%%%%%%%%%%%

@inproceedings{BoldiV04,
  author    = {Paolo Boldi and
               Sebastiano Vigna},
  title     = {The {Webgraph} framework {I}: compression techniques},
  booktitle = {WWW},
  year      = {2004}
}

@inproceedings{HeWYY05,
  author    = {Hao He and
               Haixun Wang and
               Jun Yang and
               Philip S. Yu},
  title     = {Compact reachability labeling for graph-structured data},
  booktitle = {CIKM},
  year      = {2005}
}

@inproceedings{KLMPR09,
  author    = {Flavio Chierichetti and
               Ravi Kumar and
               Silvio Lattanzi and
               Michael Mitzenmacher and
               Alessandro Panconesi and
               Prabhakar Raghavan},
  title     = {On compressing social networks},
  booktitle = {KDD},
  year      = {2009}
}

%%%%%%%%%%%%% Strong Simulation %%%%%%%%%%%%%%%%%
@inproceedings{Grohe10,
  author    = {Martin Grohe},
  title     = {From polynomial time queries to graph structure theory},
  booktitle = {ICDT},
  year      = {2010}
}

@article{DovierP03,
  author    = {Agostino Dovier and
               Carla Piazza},
  title     = {The Subgraph Bisimulation Problem},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {15},
  number    = {4},
  year      = {2003},
  pages     = {1055-1056}
}

@article{Buchan2004,
title = "The boundaries of trust: own and others' actions in the {US} and {China}",
journal = "Journal of Economic Behavior \& Organization",
volume = "55",
number = "4",
pages = "485-504",
year = "2004",
author = "Nancy Buchan and Rachel Croson"
}

@inproceedings{TerveenM05,
  author    = {Loren G. Terveen and
               David W. McDonald},
  title     = {Social matching: A framework and research agenda},
  booktitle = {ACM Trans. Comput.-Hum. Interact.},
  year      = {2005},
  pages     = {401-434}
  }
@misc{LinkedIn,
  title     = {{LinkedIn}},
  note = {{\sl www.linkedin.com}}
}

%%%%%%%%%%%%%%%%% Published Papers %%%%%%%%%%%%%%%%%%%%

@inproceedings{pvldb10,
 author = {Wenfei Fan and  Jianzhong Li and Shuai Ma
             and Hongzhi Wang and Yinghui Wu},
 title = {Graph Homomorphism Revisited for Graph Matching},
 booktitle = {PVLDB},
 year = {2010}
 }

@INPROCEEDINGS{gpm-vldb,
    AUTHOR = {Wenfei Fan and Jianzhong Li and Shuai Ma and Nan Tang and Yinghui Wu and Yunpeng Wu},
    TITLE = {Graph Pattern Matching: From Intractability to Polynomial Time},
    BOOKTITLE = "PVLDB",
    YEAR = {2010}   }


@inproceedings{gpmicde,
  author    = {Wenfei Fan and
               Jianzhong Li and
               Shuai Ma and
               Nan Tang and
               Yinghui Wu},
  title     = {Adding regular expressions to graph reachability and pattern
               queries},
  booktitle = {ICDE},
  year      = {2011}
}

@inproceedings{sigmod11,
 author = {Wenfei Fan and Jianzhong Li and Zijing Tan and Xin Wang and
          Yinghui Wu},
 title = {Incremental Graph Pattern Matching},
 booktitle = {SIGMOD},
 year = {2011}
 }

@inproceedings{strong-simulation, 
  author    = {Shuai Ma and Yang Cao and Wenfei Fan and
                  Jinpeng Huai  and Tianyu Wo},
  title     = {Capturing Topology in Graph Pattern Matching},
  booktitle = {PVLDB},
  year      = {2012}
}



@inproceedings{qp-compression,
 author =        {Wenfei Fan and  Xin Wang and Yinghui Wu},
  title =        {Query Preserving Graph Compression},
   booktitle = {SIGMOD},
  year      = {2012}
}

@inproceedings{dis-reach,
 author =        {Wenfei Fan and  Xin Wang and Yinghui Wu},
  title =        {Evaluating Reachability Queries on Distributed Graphs},
  booktitle = {VLDB},
  year      = {2012}
}


@inproceedings{CongFK07,
  author    = {Gao Cong and
               Wenfei Fan and
               Anastasios Kementsietsidis},
  title     = {Distributed query evaluation with performance guarantees},
  booktitle = {SIGMOD},
  year      = {2007}
}



@inproceedings{BunemanCFK06,
  author    = {Peter Buneman and
               Gao Cong and
               Wenfei Fan and
               Anastasios Kementsietsidis},
  title     = {Using Partial Evaluation in Distributed Query Evaluation},
  booktitle = {VLDB},
  year      = {2006},
  pages     = {211-222}}
  


%%%%%%%%%%%%%%% Keyword Searches

@INCOLLECTION{keyword-survey,
    AUTHOR={Haixun Wang and Charu Aggarwal},
    TITLE={A Survey of Algorithms for Keyword Search on Graph Data},
    BOOKTITLE={Managing and Mining Graph Data},
    PUBLISHER={Springer},
    YEAR={2010}}

@article{keyword-survey2,
title = "Keyword Search in Relational Databases: A Survey",
journal = "IEEE Data Eng. Bull.",
volume = "33",
number = "1",
pages = "67-78",
year = "2010",
author = "Jeffrey Xu Yu and Lu Qin and Lijun Chang"
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@article{preprocessing,
  author    = {Marco Cadoli and
               Francesco M. Donini and
               Paolo Liberatore and
               Marco Schaerf},
  title     = {Preprocessing of Intractable Problems},
  journal   = {Inf. Comput.},
  volume    = {176},
  number    = {2},
  year      = {2002},
  pages     = {89-120}
}

@article{DBLP:journals/jcss/SuciuT97,
  author    = {Dan Suciu and
               Val Tannen},
  title     = {A Query Language for {NC}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {55},
  number    = {2},
  year      = {1997},
  pages     = {299-321},
  ee        = {http://dx.doi.org/10.1006/jcss.1997.1525},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{DBLP:conf/lics/Grohe08,
  author    = {Martin Grohe},
  title     = {The Quest for a Logic Capturing PTIME},
  booktitle = {LICS},
  year      = {2008},
  pages     = {267-271},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/LICS.2008.11},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/cacm/Valiant90,
  author    = {Leslie G. Valiant},
  title     = {A Bridging Model for Parallel Computation},
  journal   = {Commun. ACM},
  volume    = {33},
  number    = {8},
  year      = {1990},
  pages     = {103-111},
  ee        = {http://doi.acm.org/10.1145/79173.79181},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{DBLP:journals/cacm/CullerKPSSSSE96,
  author    = {David E. Culler and
               Richard M. Karp and
               David A. Patterson and
               Abhijit Sahay and
               Eunice E. Santos and
               Klaus E. Schauser and
               Ramesh Subramonian and
               Thorsten von Eicken},
  title     = {LogP: A Practical Model of Parallel Computation},
  journal   = {Commun. ACM},
  volume    = {39},
  number    = {11},
  year      = {1996},
  pages     = {78-85},
  ee        = {http://doi.acm.org/10.1145/240455.240477},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{Limits,
 author = {Raymond Greenlaw and H. James Hoover and Walter L. Ruzzo},
 title = {Limits to Parallel Computation: P-Completeness Theory},
 year = {1995},
 publisher = {Oxford University Press}
} 

@incollection{catalog,
  author    = {David S. Johnson},
  title     = {A Catalog of Complexity Classes},
  booktitle = {Handbook of Theoretical Computer Science, Volume A: Algorithms
               and Complexity (A)},
  year      = {1990},
  pages     = {67-161},
   publisher = {The {MIT} Press}
}

@article{incremental-complexity,
  author    = {Peter Bro Miltersen and
               Sairam Subramanian and
               Jeffrey Scott Vitter and
               Roberto Tamassia},
  title     = {Complexity Models for Incremental Computation},
  journal   = {TCS},
  volume    = {130},
  number    = {1},
  year      = {1994},
  pages     = {203-236}
}

@inproceedings{MapReduce,
  author    = {Howard J. Karloff and
               Siddharth Suri and
               Sergei Vassilvitskii},
  title     = {A Model of Computation for {MapReduce}},
  booktitle = {SODA},
  year      = {2010},
  pages     = {938-948}
}

@article{PB,
  author    = {Alexander S. Szalay and
               Jim Gray and
               Jan vandenBerg},
  title     = {Petabyte Scale Data Mining: Dream or Reality?},
  journal   = {CoRR},
  volume    = {cs.DB/0208013},
  year      = {2002}
}

@inproceedings{DBLP:conf/edbt/BorkarCL12,
  author    = {Vinayak R. Borkar and
               Michael J. Carey and
               Chen Li},
  title     = {Inside   ``Big Data management'': ogres, onions, or parfaits?},
  booktitle = {EDBT},
  year      = {2012}
}

@proceedings{DBLP:conf/edbt/2012,
  editor    = {Elke A. Rundensteiner and
               Volker Markl and
               Ioana Manolescu and
               Sihem Amer-Yahia and
               Felix Naumann and
               Ismail Ari},
  title     = {15th International Conference on Extending Database Technology,
               EDBT '12, Berlin, Germany, March 27-30, 2012, Proceedings},
  booktitle = {EDBT},
  publisher = {ACM},
  year      = {2012},
  isbn      = {978-1-4503-0790-1},
  ee        = {http://dl.acm.org/citation.cfm?id=2247596},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{DBLP:journals/sigmod/Hellerstein10,
  author    = {Joseph M. Hellerstein},
  title     = {The declarative imperative: experiences and conjectures
               in distributed logic},
  journal   = {SIGMOD Record},
  volume    = {39},
  number    = {1},
  year      = {2010},
  pages     = {5-19},
  ee        = {http://doi.acm.org/10.1145/1860702.1860704},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{preprocessing1,
  author    = {Johannes Fischer and
               Volker Heun},
  title     = {Space-Efficient Preprocessing Schemes for Range Minimum
               Queries on Static Arrays},
  journal   = {SICOMP},
  volume    = {40},
  number    = {2},
  year      = {2011},
  pages     = {465-492}
}
@article{LCA,
  author    = {Michael A. Bender and
               Martin Farach-Colton and
               Giridhar Pemmasani and
               Steven Skiena and
               Pavel Sumazin},
  title     = {Lowest common ancestors in trees and directed acyclic graphs},
  journal   = {J. Algorithms},
  volume    = {57},
  number    = {2},
  year      = {2005},
  pages     = {75-94}
}

@INPROCEEDINGS{Miltersen99cellprobe,
    author = {Peter Bro Miltersen},
    title = {Cell Probe Complexity - a Survey},
    booktitle = {FSTTCS}, 
    year = {1999}
}

@book{PCT,
 author = {J. Flum and M. Grohe},
 title = {Parameterized Complexity Theory},
 year = {2006},
 publisher = {Springer}
} 

@article{compression,
  author    = {Danny Harnik and
               Moni Naor},
  title     = {On the Compressibility of {NP} Instances and Cryptographic
               Applications},
  journal   = {SICOMP},
  volume    = {39},
  number    = {5},
  year      = {2010},
  pages     = {1667-1713}
}

@inproceedings{sublinear-1,
  author    = {Artur Czumaj and
               Christian Sohler},
  title     = {Sublinear-time Algorithms},
  booktitle = {Property Testing},
  year      = {2010},
  pages     = {41-64}
}


@article{sublinear-2,
  author    = {Dana Ron},
  title     = {Algorithmic and Analysis Techniques in Property Testing},
  journal   = {{FnT-TCS}},
  volume    = {5},
  number    = {2},
  year      = {2010},
  pages     = {73-205}
}

@article{sublinear2-full,
  author    = {Dana Ron},
  title     = {Algorithmic and Analysis Techniques in Property Testing},
  journal   = {Foundations and Trends in Theoretical Computer Science},
  volume    = {5},
  number    = {2},
  year      = {2010},
  pages     = {73-205}
}


@Misc{SSD,
 author =        {Glenn Santos},
  title =        {{SSD} Ranking: The Fastest Solid State Drives},
  howpublished = {\\ 
{\sl http://www.fastestssd.com/featured/ssd-rankings-the-fastest-solid-state-drives/\#pcie}},
  month = {Oct},
  year = {2012}
}

@inproceedings{SIGMOD12,
  author    = {Wenfei Fan and
               Jianzhong Li and
               Xin Wang and
               Yinghui Wu},
  title     = {Query preserving graph compression},
  booktitle = {SIGMOD},
  year      = {2012},
  pages     = {157-168}
}


@Misc{bigdata,
 author =        {H. V. {Jagadish et al.}},
  title =        {Challenges  and  Opportunities  with  Big  Data:  
  A  community  white  paper  developed  by  leading  researchers  across  the  United  States}, 
 howpublished = {\\ {\sl cra.org/ccc/docs/init/bigdatawhitepaper.pdf}},
  year = {2012}
}

@article{FaginLN03,
  author    = {Ronald Fagin and
               Amnon Lotem and
               Moni Naor},
  title     = {Optimal aggregation algorithms for middleware},
  journal   = {JCSS},
  volume    = {66},
  number    = {4},
  year      = {2003},
  pages     = {614-656}
}


@inproceedings{DBLP:conf/pods/KoutrisS11,
  author    = {Paraschos Koutris and
               Dan Suciu},
  title     = {Parallel evaluation of conjunctive queries},
  booktitle = {PODS},
  year      = {2011},
  pages     = {223-234},
  ee        = {http://doi.acm.org/10.1145/1989284.1989310},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/edbt/AfratiU12,
  author    = {Foto N. Afrati and
               Jeffrey D. Ullman},
  title     = {Transitive closure and recursive Datalog implemented on
               clusters},
  booktitle = {EDBT},
  year      = {2012}
}


@INCOLLECTION{AY2007,
    AUTHOR={Charu C. Aggarwal and Philip S. Yu},
    TITLE={A Survey of Synopsis Construction in Data Streams},
    BOOKTITLE={Data Streams - Models and Algorithms},
    EDITOR={Charu C. Aggarwal},
    PUBLISHER={Springer},
    YEAR={2007}}

@inproceedings{quantiles,
  author    = {Gurmeet Singh Manku and Sridhar Rajagopalan and Bruce G. Lindsay},
  title     = {Approximate Medians and other Quantiles in One Pass and with Limited Memory},
  booktitle = {SIGMOD},
  year      = {1998}
}

@inproceedings{quantiles-1,
  author    = {Michael Greenwald and Sanjeev Khanna},
  title     = {Space-Efficient Online Computation of Quantile Summaries},
  booktitle = {SIGMOD},
  year      = {2001}
}


@article{lossy,
  author    = {Tomasz Luczak and Wojciech Szpankowski},
  title     = {A suboptimal lossy data compression based on approximate pattern matching},
  journal   = {IEEE Trans.~on Inf.~Theory},
  volume    = {43},
  number    = {5},
  year      = {1997},
  pages     = {1439-1451}
}

@inproceedings{distance-query,
  author    = {Rachit Agarwal and Philip Brighten Godfrey and Sariel Har-Peled},
  title     = {Approximate distance queries and compact routing in sparse graphs},
  booktitle = { INFOCOM},
  year      = {2011}
}

@article{histogram1, 
  author    = {Sudipto Guha and Nick Koudas and Kyuseok Shim},
  title     = {Approximation and streaming algorithms for histogram construction problems},
  journal   = {TODS},
  volume    = {31},
  number    = {1},
  year      = {2006},
  pages     = {396-438}
}

@inproceedings{wavelet-1,
  author    = {Minos N. Garofalakis and Amit Kumar},
  title     =  {Deterministic Wavelet Thresholding for Maximum-Error Metrics},
  booktitle = {PODS},
  year      = {2004}
}

@inproceedings{wavelet-2,
  author    = {Minos N. Garofalakis and Phillip B. Gibbons},
  title     =  {Wavelet synopses with error guarantees},
  booktitle = {SIGMOD},
  year      = {2002}
}

@article{wavelet3,
  title={Hierarchical synopses with optimal error guarantees},
  author={Karras, Panagiotis and Mamoulis, Nikos},
  journal={TODS},
  year={2008},
}

@article{histogram2, 
  author    = {Viswanath Poosala and Venkatesh Ganti and Yannis E. Ioannidis},
  title     = {Approximate Query Answering using Histograms},
  journal   = {IEEE Data Eng. Bull},
  volume    = {22},
  number    = {4},
  year      = {1999},
  pages     = {5-14}
}

@inproceedings{clustering,
  author    = {Charu C. Aggarwal and Jiawei Han and Jianyong Wang and Philip S. Yu},
  title     =  {A Framework for Clustering Evolving Data Streams},
  booktitle = {VLDB},
  year      = {2003}
}

@inproceedings{retireval,
  author    = {Aris Anagnostopoulos and
               Luca Becchetti and Stefano Leonardi and Ida Mele and Piotr Sankowski},
  title     =  {Stochastic query covering},
  booktitle = {WSDM},
  year      = {2011}
}

@inproceedings{Simrank,
  author    = {Weiren Yu and Wenjie Zhang and Xuemin Lin and Qing Zhang and Jiajin Le},
  title     =  { A space and time efficient algorithm for SimRank computation},
  booktitle = {WWW},
  year      = {2012}
}



@inproceedings{BD-tractable,
 author =        {Wenfei Fan and  Floris Geerts and Frank Neven},
  title =        {Making queries tractable on big data with preprocessing},
  booktitle = {VLDB},
  year = 2013
}



@book{NPO,
  title={Complexity and Approximability Properties: Combinatorial Optimization Problems and Their Approximability Properties}, 
  author={G. Ausiello and P. Crescenzi and G. Gambosi and V. Kann and A. Marchetti-Spaccamela and M. Protasi},
  year = {1999}
}


@Misc{Lin,

 author =        {{CTO of an anonymous company}},

  title =        {Personal communication},
  month = {March}, 
  year =         2013

}
@Article{viewsurvey,

  author =       {Alon Y Halevy},

  title =        {Theory of Answering Queries Using Views},

  journal =      {SIGMOD Record},

  volume  =      29,

  number  =      4,

  year =         2001

}
@article{Halevy01,
  author    = {Alon Y. Halevy},
  title     = {Answering queries using views: A survey},
  journal   = {VLDB J.},
  volume    = {10},
  number    = {4},
  year      = {2001},
  pages     = {270-294}}


@article{TZ2005,
  author    = {Mikkel Thorup and Uri Zwick},
  title     = {Approximate distance oracles},
  journal   = {JACM},
  volume    = {52},
  number    = {1},
  year      = {2005},
  pages     = {1-24}}


@article{Ilyas:2008,
 author = {Ilyas, Ihab F. and Beskales, George and Soliman, Mohamed A.},
 title = {A survey of top-k query processing techniques in relational database systems},
 journal = {ACM Comput. Surv.},
 volume = {40},
number = {4},
 year = {2008},
 pages = {11:1--11:58},
 articleno = {11}
}


@Misc{views,
 author =        {Wenfei Fan and  Xin Wang and Yinghui Wu},
  title =        {Graph Pattern Matching Using Views},
  year = 2013, 
  howpublished = {Unpublished manuscript}
}

@inproceedings{tug,
 author = {Joshua Spiegel and Neoklis Polyzotis},
 title = {{TuG} synopses for approximate query answering},
 booktitle = {TODS},
 year = {2009}
}


@inproceedings{histogram-3,
  author    = {H. V. Jagadish and Nick Koudas and S. Muthukrishnan
  and Viswanath Poosala and Kenneth C. Sevcik and Torsten Suel},
  title     =  {Optimal Histograms with Quality Guarantees},
  booktitle = {VLDB},
  year      = {2009}
}

@inproceedings{wavelet4,
  author    = {Jeffrey Scott Vitter and Min Wang},
  title     =  {Approximate Computation of Multidimensional 
   Aggregates of Sparse Data Using Wavelets},
  booktitle = {SIGMOD},
  year      = {1999}
}
@article{datareduction,
  author    = {Daniel Barbar{\'a} and
               William DuMouchel and
               Christos Faloutsos and
               Peter J. Haas and
               Joseph M. Hellerstein and
               Yannis E. Ioannidis and
               H. V. Jagadish and
               Theodore Johnson and
               Raymond T. Ng and
               Viswanath Poosala and
               Kenneth A. Ross and
               Kenneth C. Sevcik},
  title     = {The New Jersey Data Reduction Report},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {20},
  number    = {4},
  year      = {1997}
}

@inproceedings{histogram-knn,
  author    = {Liang Jin and
               Nick Koudas and
               Chen Li},
  title     = {NNH: Improving Performance of Nearest-Neighbor Searches
               Using Histograms},
  booktitle = {EDBT},
  year      = {2004}
}
@inproceedings{histogram-selection-1,
  author    = {Hai Wang and
               Kenneth C. Sevcik},
  title     = {A multi-dimensional histogram for selectivity estimation
               and fast approximate query answering},
  booktitle = {CASCON},
  year      = {2003}
}
@article{histogram-appro,
  author    = {Viswanath Poosala and
               Venkatesh Ganti and
               Yannis E. Ioannidis},
  title     = {Approximate Query Answering using Histograms},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {22},
  number    = {4},
  year      = {1999}
}

@inproceedings{histogram-set,
  author    = {Yannis E. Ioannidis and
               Viswanath Poosala},
  title     = {Histogram-Based Approximation of Set-Valued Query-Answers},
  booktitle = {VLDB},
  year      = {1999}
}
@inproceedings{histogram-multidimension,
  author    = {Todd Eavis and
               Alex Lopez},
  title     = {Rk-hist: an r-tree based histogram for multi-dimensional
               selectivity estimation},
  booktitle = {CIKM},
  year      = {2007}
}
@inproceedings{histogram-xml,
  author    = {Wei Wang and
               Haifeng Jiang and
               Hongjun Lu and
               Jeffrey Xu Yu},
  title     = {Bloom Histogram: Path Selectivity Estimation for XML Data
               with Updates},
  booktitle = {VLDB},
  year      = {2004}
}
@inproceedings{histogram-xml2,
  author    = {Lipyeow Lim and
               Min Wang and
               Jeffrey Scott Vitter},
  title     = {CXHist : An On-line Classification-Based Histogram for XML
               String Selectivity Estimation},
  booktitle = {VLDB},
  year      = {2005}
}
@inproceedings{histogram4,
  title={Compact histograms for hierarchical identifiers},
  author={Reiss, Frederick and Garofalakis, Minos and Hellerstein, Joseph M},
  booktitle={VLDB},
  year={2006},
}
@inproceedings{histogram-rev,
    author = {Alin Dobra},
    title = {Histograms revisited: When are histograms the best approximation method for aggregates over joins},
    booktitle = {PODS},
    year = {2005},
}

@inproceedings{sampling1,
 author = {Hellerstein, Joseph M. and Haas, Peter J. and Wang, Helen J.},
 title = {Online Aggregation},
 booktitle = {SIGMOD},
 year = {1997},
} 
@inproceedings{sampling2,
    author = {Swarup Acharya and Phillip B. Gibbons and Viswanath Poosala},
    title = {Congressional samples for approximate answering of group-by queries},
    booktitle = {SIGMOD},
    year = {2000},
}
@inproceedings{sampling3,
  author    = {Brian Babcock and
               Surajit Chaudhuri and
               Gautam Das},
  title     = {Dynamic Sample Selection for Approximate Query Processing},
  booktitle = {SIGMOD},
  year      = {2003}
}
@book{cluster1,
  author    = {L. Kaufman and
               P. J. Rousseeuw},
  title     = {Finding Groups in Data: An Introduction to Cluster Analysis},
  publisher = {John Wiley},
  year      = {1990}
}
@inproceedings{cluster2,
  author    = {Martin Ester and
               Hans-Peter Kriegel and
               J{\"o}rg Sander and
               Xiaowei Xu},
  title     = {A Density-Based Algorithm for Discovering Clusters in Large
               Spatial Databases with Noise},
  booktitle = {KDD},
  year      = {1996}
}
@inproceedings{joinsynopsis,
  author    = {Swarup Acharya and
               Phillip B. Gibbons and
               Viswanath Poosala and
               Sridhar Ramaswamy},
  title     = {Join Synopses for Approximate Query Answering},
  booktitle = {SIGMOD},
  year      = {1999}
}
@inproceedings{synopsisstructure,
  author    = {Phillip B. Gibbons and
               Yossi Matias},
  title     = {Synopsis Data Structures for Massive Data Sets},
  booktitle = {SODA},
  year      = {1999}
}
@inproceedings{hyperrelation,
  author    = {Hui Wang and
               Ivo D{\"u}ntsch and
               David A. Bell},
  title     = {Data Reduction Based on Hyper Relations},
  booktitle = {KDD},
  year      = {1998}
}
@inproceedings{PIQL,
  author    = {Michael Armbrust and
               Stephen Tu and
               Armando Fox and
               Michael J. Franklin and
               David A. Patterson and
               Nick Lanham and
               Beth Trushkowsky and
               Jesse Trutna},
  title     = {{PIQL}: a performance insightful query language},
  booktitle = {SIGMOD},
  year      = {2010}
}
@inproceedings{increscale,
  author    = {Michael Armbrust and
               Eric Liang and
               Tim Kraska and
               Armando Fox and
               Michael J. Franklin and
               David Patterson},
  title     = {Generalized scale independence through incremental precomputation},
  booktitle = {SIGMOD},
  year      = {2013}
}
@inproceedings{scale,
  author    = {Michael Armbrust and
               Armando Fox and
               David A. Patterson and
               Nick Lanham and
               Beth Trushkowsky and
               Jesse Trutna and
               Haruki Oh},
  title     = {SCADS: Scale-Independent Storage for Social Computing Applications},
  booktitle = {CIDR},
  year      = {2009}
}
@inproceedings{app-fingerprints,
  author    = {Yoram Bachrach and
               Ely Porat},
  title     = {Sketching for Big Data Recommender Systems Using Fast Pseudo-random
               Fingerprints},
  booktitle = {ICALP},
  year      = {2013}
}
@inproceedings{app-coreset-sensors,
  author    = {Dan Feldman and
               Andrew Sugaya and
               Daniela Rus},
  title     = {An effective coreset compression algorithm for large scale
               sensor networks},
  booktitle = {IPSN},
  year      = {2012}
}
@inproceedings{app-coreset-dist,
author    = {Bernd G{\"a}rtner and
             Martin Jaggi},
title     = {Coresets for polytope distance},
booktitle = {SCG},
year      = {2009}
}

@inproceedings{app-coreset-ML,
author    = {Marcel R. Ackermann, Johannes Bl\"{o}mer},
title     = {Coresets and approximate clustering for Bregman divergences},
booktitle = {SODA},
year      = {2009}
}
@article{tao2013minimal,
  title={Minimal {MapReduce} algorithms},
  author={Tao, Yufei and Lin, Wenqing and Xiao, Xiaokui},
  journal={SIGMOD},
  year={2013}
}
@article{propertytesting,
  author    = {Dana Ron},
  title     = {Algorithmic and Analysis Techniques in Property Testing},
  journal   = {FTTCS},
  volume    = {5},
  number    = {2},
  year      = {2009}
}
@article{sublinear,
  title={Sublinear time algorithms},
  author={Rubinfeld, Ronitt and Shapira, Asaf},
  journal={SIAM Journal on Discrete Mathematics},
  volume={25},
  number={4},
  year={2011}
}
@book{multi-index,
  title={Foundations of multidimensional and metric data structures},
  author={Samet, Hanan},
  year={2006},
  publisher={Morgan Kaufmann}
}
@article{synopses,
  title={Synopses for massive data: Samples, histograms, wavelets, sketches},
  author={Cormode, Graham and Garofalakis, Minos and Haas, Peter J and Jermaine, Chris},
  journal={FTDB},
  volume={4},
  number={1--3},
  year={2012}
}

@inproceedings{RankSQL,
  title={RankSQL: query algebra and optimization for relational top-k queries},
  author={Li, Chengkai and Chang, Kevin Chen-Chuan and Ilyas, Ihab F and Song, Sumin},
  booktitle={SIGMOD},
  year={2005}
}
@article{boundedSPC,
  author    = {Yang Cao and Wenfei Fan and Tianyu Wo and Wenyuan Yu},
  title     = {Bounded Conjunctive Queries},
  journal = {PVLDB},
  year      = {2014}
}
@inproceedings{fullCQ,
  author    = {Albert Atserias and
               Martin Grohe and
               D{\'{a}}niel Marx},
  title     = {Size Bounds and Query Plans for Relational Joins},
  booktitle = {FOCS},
  year      = {2008}
}
@inproceedings{MAC,
  title={Histogram-based approximation of set-valued query-answers},
  author={Ioannidis, Yannis E and Poosala, Viswanath},
  booktitle={VLDB},
  year={1999}
}
@inproceedings{EMD,
  author    = {Yossi Rubner and
               Carlo Tomasi and
               Leonidas J. Guibas},
  title     = {A Metric for Distributions with Applications to Image Databases},
  booktitle = {{ICCV}},
  year      = {1998}
}
@article{AQP-wavelet,
  author    = {Kaushik Chakrabarti and
               Minos N. Garofalakis and
               Rajeev Rastogi and
               Kyuseok Shim},
  title     = {Approximate query processing using wavelets},
  journal   = {{VLDB} J.},
  volume    = {10},
  number    = {2-3},
  year      = {2001}
}
@inproceedings{relaxation,
  title={Relaxing join and selection queries},
  author={Koudas, Nick and Li, Chen and Tung, Anthony KH and Vernica, Rares},
  booktitle={VLDB},
  year={2006}
}


@inproceedings{wavelet,
 author = {Chakrabarti, Kaushik and Garofalakis, Minos N. and Rastogi, Rajeev and Shim, Kyuseok},
 title = {Approximate Query Processing Using Wavelets},
 booktitle = {VLDB},
 year = {2000},
} 

@inproceedings{blinkdb,
 author = {Agarwal, Sameer and Mozafari, Barzan and Panda, Aurojit and Milner, Henry and Madden, Samuel and Stoica, Ion},
 title = {{BlinkDB}: Queries with Bounded Errors and Bounded Response Times on Very Large Data},
 booktitle = {EuroSys},
 year = {2013},
} 

@inproceedings{hausdorff,
  title={Comparing images using the {Hausdorff} distance},
  author={Huttenlocher, Daniel P. and Klanderman, Gregory A. and Rucklidge, William J},
  booktitle={TPAMI},
  year={1993},
}


@inproceedings{AQPsurvey,
 author = {Garofalakis, Minos N. and Gibbon, Phillip B.},
 title = {Approximate Query Processing: Taming the TeraBytes},
 booktitle = {VLDB},
 year = {2001},
} 

@Misc{fullv,
  author =        {},
  title =        {Full paper},
  howpublished = {{\sl  http://homepages.inf.ed.ac.uk/s1165433/RB.pdf}}
}

@inproceedings{bootstrap1,
  title={Relational confidence bounds are easy with the bootstrap},
  author={Pol, Abhijit and Jermaine, Christopher},
  booktitle={SIGMOD},
  year={2005},
}

@inproceedings{bootstrap2,
  title={The analytical bootstrap: a new method for fast error estimation in approximate query processing},
  author={Zeng, Kai and Gao, Shi and Mozafari, Barzan and Zaniolo, Carlo},
  booktitle={SIGMOD},
  year={2014}
}

@Misc{tripadvisor,
 author = {},
 title = {Tripadvisor},
 howpublished = {{\sl http://www.tripadvisor.co.uk/PressCenter-c4-Fact\_Sheet.html}}
}

@inproceedings{PODS14,
  author = {Wenfei Fan and Floris Geerts and Leonid Libkin},
  title =    {On Scale Independence for Querying Big Data},
   booktitle =     {PODS},
  year = {2014}
}

@inproceedings{ICDE2015,
author    = {Yang Cao and Wenfei Fan and Ruizhe Huang},
title     = {Making Pattern Queries Bounded in Big Graphs},
booktitle = {ICDE},
year = {2015}
}

@book{multi-idx,
 author = {Samet, Hanan},
 title = {Foundations of Multidimensional and Metric Data Structures},
 year = {2005},
 publisher = {Morgan Kaufmann Publishers Inc.},
} 

@article{kdtree,
 author = {Bentley, Jon Louis},
 title = {Multidimensional Binary Search Trees Used for Associative Searching},
 journal = {Commun. ACM},
 year = {1975},
}

@article{rangetree,
  title={Decomposable searching problems},
  author={Bentley, Jon Louis},
  journal={Information Processing Letters},
  year={1979},
}

@book{rtree,
  title={R-trees: a dynamic index structure for spatial searching},
  author={Guttman, Antonin},
  year={1984},
  publisher={ACM}
}

@inproceedings{mhist,
  title={Selectivity estimation without the attribute value independence assumption},
  author={Poosala, Viswanath and Ioannidis, Yannis E},
  booktitle={VLDB},
  year={1997}
}

@inproceedings{stholes,
  title={STHoles: a multidimensional workload-aware histogram},
  author={Bruno, Nicolas and Chaudhuri, Surajit and Gravano, Luis},
  booktitle={SIGMOD Record},
  year={2001},
}

@inproceedings{rk-hist,
  title={Rk-hist: an r-tree based histogram for multi-dimensional selectivity estimation},
  author={Eavis, Todd and Lopez, Alex},
  booktitle={CIKM},
  year={2007},
}

@inproceedings{haar+,
  title={The Haar+ tree: a refined synopsis data structure},
  author={Karras, Panagiotis and Mamoulis, Nikos},
  booktitle={ICDE},
  year={2007},
}

@inproceedings{relaxation1,
  title={Relaxing join and selection queries},
  author={Koudas, Nick and Li, Chen and Tung, Anthony KH and Vernica, Rares},
  booktitle={VLDB},
  year={2006},
}

@incollection{relaxation-survey,
  title={Approximate queries with adaptive processing},
  author={Catania, Barbara and Guerrini, Giovanna},
  booktitle={Advanced Query Processing},
  year={2013},
  publisher={Springer}
}

@inproceedings{relaxation2,
  title={Generalization and a framework for query modification},
  author={Chaudhuri, Surajit},
  booktitle={ICDE},
  year={1990},
}

@inproceedings{relaxation3,
  title={Query relaxation using malleable schemas},
  author={Zhou, Xuan and Gaugaz, Julien and Balke, Wolf-Tilo and Nejdl, Wolfgang},
  booktitle={SIGMOD},
  year={2007},
}

@inproceedings{sketch1,
  title={Sketching streams through the net: Distributed approximate query tracking},
  author={Cormode, Graham and Garofalakis, Minos},
  booktitle={VLDB},
  year={2005},
}

@inproceedings{sketch2,
  title={Approximate counts and quantiles over sliding windows},
  author={Arasu, Arvind and Manku, Gurmeet Singh},
  booktitle={PODS},
  year={2004},
}

@article{stratifiedsampling,
  title={Optimized stratified sampling for approximate query processing},
  author={Chaudhuri, Surajit and Das, Gautam and Narasayya, Vivek},
  journal={TODS},
  volume={32},
  number={2},
  year={2007}
}
@inproceedings{sigmod14,
  title={Querying big graphs within bounded resources},
  author={Fan, Wenfei and Wang, Xin and Wu, Yinghui},
  booktitle={SIGMOD},
  year={2014}
}
@article{anytime,
  title={Using anytime algorithms in intelligent systems},
  author={Zilberstein, Shlomo},
  journal={AI magazine},
  volume={17},
  number={3},
  year={1996}
}

@inproceedings{abiteboul98,

  author =   {Serge Abiteboul and Oliver M. Duschka},

  title =    {Complexity of Answering Queries Using Materialized Views},

  booktitle =    {PODS},

  year =     1998

}

@inproceedings{ThayerSFR12,
  author    = {Jordan Tyler Thayer and
               Roni Stern and
               Ariel Felner and
               Wheeler Ruml},
  title     = {Faster Bounded-Cost Search Using Inadmissible Estimates},
  booktitle = {ICAPS},
  year      = {2012}
}

@inproceedings{stern2011potential,
  title={Potential Search: A Bounded-Cost Search Algorithm.},
  author={Stern, Roni Tzvi and Puzis, Rami and Felner, Ariel},
  booktitle={ICAPS},
  year={2011}
}

@inproceedings{histo-kd1,
  title={Selectivity estimation without the attribute value independence assumption},
  author={Poosala, Viswanath and Ioannidis, Yannis E},
  booktitle={VLDB},
  year={1997}
}

@inproceedings{histo-kd2,
  title={Multi-dimensional histograms with tight bounds for the error},
  author={Baltrunas, Linas and Mazeika, Arturas and Bohlen, Michael},
  booktitle={Database Engineering and Applications Symposium (IDEAS)},
  year={2006},
}

@inproceedings{histo-r1,
  title={Equi-depth multidimensional histograms},
  author={Muralikrishna, M and DeWitt, David J},
  booktitle={SIGMOD},
  year={1988},
}

@inproceedings{histo-r2,
  author = {Gunopulos, Dimitrios and Kollios, George and Tsotras, Vassilis J. and Domeniconi, Carlotta},
  title = {Approximating Multi-dimensional Aggregate Range Queries over Real Attributes},
  booktitle = {SIGMOD},
  year = {2000},
} 

@inproceedings{histo-r3,
  author = {Nicolas Bruno and Surajit Chaudhuri and Luis Gravano},
  title = {STHoles: a multidimensional workload-aware histogram},
  booktitle = {SIGMOD},
  year = {2001},
}

@MISC{SNAP,
  Title = {{Gowalla and Brightkite}},
  note = {\\{\sl http://snap.stanford.edu/data/}}
}

@MISC{brightkite,
  Title = {{Brightkite}},
  note = {{\sl http://snap.stanford.edu/data/loc-brightkite.html}}
}

@MISC{OSM,
  Title = {{OpenStreetMap}},
  note = {{\sl http://wiki.openstreetmap.org/}}
}

@MISC{FLT,
  Title = {{FLT}},
  note = {{\sl http://www.transtats.bts.gov/TableInfo.asp?Table\_ID=236}}
}

@MISC{tpch,
  Title = {{TPC-H}},
  author = {TPC},
  year = {2019},
  note = {{\sl http://www.tpc.org/tpch/}}
}

@MISC{tpcds,
  Title = {{TPC-DS}},
  author = {TPC},
  year = 2019,
  note = {{\sl http://www.tpc.org/tpcds/}}
}


@inproceedings{PODS15,
  author = {Wenfei Fan and Floris Geerts and Yang Cao and Ting Deng},
  title =    {Querying Big Data by Accessing Small Data},
   booktitle =     {PODS},
  year = {2015}
}
@ARTICLE{tane,
  author = {Y Huhtala and Juha K\"{a}rkk\:{a}inen and Pasi Porkka
   and Hannu Toivonen},
  title = {{TANE}: An Efficient Algorithm for Discovering Functional
          and Approximate Dependencies},
  journal = {Comput. J.},
  year = {1999},
  volume = {42},
  pages = {100-111},
  number = {2}
}

@inproceedings{facebook-statis,
  title={Collecting and Analyzing Data from E-Government Facebook Pages},
  author={Ivana Grujic and Sanja Bogdanovic-Dinic and Leonid Stoimenov},
  booktitle={ICT Innovations},
  year={2014}
}

@inproceedings{cule2015space,
  title={Space-Bounded Query Approximation},
  author={Cule, Boris and Geerts, Floris and Ndindi, Reuben},
  booktitle={ADBIS},
  year={2015}
}

@inproceedings{SIGMOD16,
author = {Yang Cao and Wenfei Fan},
title = {An Effective Syntax for Bounded Relational Queries},
booktitle = {SIGMOD},
year = {2016}
}

@inproceedings{bolin1,
author = {Bolin Ding and Silu Huang and Surajit Chaudhuri and Kaushik Chakrabarto and Chi Wang},
title = {Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee},
booktitle = {SIGMOD},
year = {2016}
}

@inproceedings{bolin2,
author = {Srikanth Kandula and Anil Shanbhag and Aleksandar Vitorovic
  and Matthaios Olma and Robert Grandl and Surajit Chaudhuri and Bolin Ding},
title = {Quickr: Lazily Approximating Complex Ad-Hoc Queries in Big Data Clusters},
booktitle = {SIGMOD},
year = {2016}
}

@book{fundamentalDB,
  title={Fundamentals of database systems},
  author={Elmasri, Ramez},
  year={2008},
  publisher={Pearson Education India}
}

@Misc{FOTP,
author = {Bureau of Transportation Statistics},
title = {National Transportation Statistics},
  howpublished = {{\sl http://www.transtats.bts.gov/DatabaseInfo.asp?DB\_ID=120}},
  year={2019}
}

@Misc{ACS,
author = {Bureau of Transportation Statistics},
title = {National Transportation Statistics},
  howpublished = {{\sl http://www.transtats.bts.gov/DatabaseInfo.asp?DB\_ID=110}},
  year={2019}
}

@Misc{ACFR,
author = {},
title = {},
  howpublished = {\sl {http://www.transtats.bts.gov/DatabaseInfo.asp?DB\_ID=135}}
}

@Misc{full,
author = {},
title = {Full version},
howpublished = {{\sl http://homepages.inf.ed.ac.uk/ycao/disAC.pdf}}
}


@Misc{facebook-constraints,
 author =        {Facebook},
  title =        {Cardinality constranints on Facebook data},
  howpublished = {\\{\sl{\url{https://www.facebook.com/help/227794810567981/community/question/?id=364005057055660}}}},
 year = {2014}
}



@Article{Li2001,
  author =       {Chen Li},
  title =        {Computing complete answers to queries in the presence of limited access patterns},
  journal =      "VLDB J.",
  volume =       12,
  number =       3,
  pages = {211-227},
  year   =  "2003"
}


@Article{limited,
  author = {Alin Deutsch and Bertram Lud\"{a}scher and Alan Nash},
  title =        {Rewriting queries using views with access patterns under integrity constraints},
  journal =      "TCS",
  volume =       371,
  number =       3,
  pages =  "200-226",
  year   =  "2007"
}

@article{MB-access-15,
  author    = {Michael Benedikt and
               Pierre Bourhis and
               Clemens Ley},
  title     = {Analysis of Schemas with Access Restrictions},
  journal   = {TODS},
  volume    = {40},
  number    = {1},
  pages     = {5},
  year      = {2015}
}

@inproceedings{MB-pods-14,
 author = {Benedikt, Michael and ten Cate, Balder and Tsamoura, Efthymia},
 title = {Generating Low-cost Plans from Proofs},
 booktitle = {PODS},
 year = {2014}
}

@inproceedings{accesslimitations,
  author    = {Andrea Cal{\`{\i}} and
               Davide Martinenghi},
  title     = {Querying Data under Access Limitations},
  booktitle = {ICDE},
  year      = {2008}
}

@article{AP-Constraint,
  title={Querying with access patterns and integrity constraints},
  author={Benedikt, Michael and Leblay, Julien and Tsamoura, Efthymia},
  journal={PVLDB},
  volume={8},
  number={6},
  year={2015}
}


@inproceedings{Nash,
  author    = {Alan Nash and Bertram Lud\"{a}scher},
  title     = {Processing First-Order Queries under Limited Access Patterns},
  booktitle = {PODS},
  year      = {2004}
}

@article{liu2010discover,
 author    = {Jixue Liu and
               Jiuyong Li and
               Chengfei Liu and
               Yongfeng Chen},
  title     = {Discover Dependencies from Data - {A} Review},
  journal   = {TKDE},
  volume    = {24},
  number    = {2},
  year      = {2012}
}


@Misc{graphSearch,
 author =        {Facebook},
  title =        {Introducing {Graph Search}},
  howpublished = {\\ {\sl https://en-gb.facebook.com/about/graphsearch}},
  year = 2013
}


@article{fan2013incremental,
  title={Incremental graph pattern matching},
  author={Fan, Wenfei and Wang, Xin and Wu, Yinghui},
  journal={TODS},
  volume={38},
  number={3},
  pages={18},
  year={2013}
}

@Misc{ACFR,
author = {},
title = {},
  howpublished = {\sl {http://www.transtats.bts.gov/DatabaseInfo.asp?DB\_ID=135}}
}

@Misc{roadsafety,
author = {},
title = {},
  howpublished = {{\sl http://data.gov.uk/dataset/road-accidents-safety-data}}
}

@Misc{naptan,
author = {},
title = {},
  howpublished = {{\sl http://data.gov.uk/dataset/naptan}}
}

@Misc{mot,
author = {},
title = {},
howpublished = {\sl {http://data.gov.uk/dataset/anonymised\_mot\_test}}
}

@article{Stockmeyer76,
  author    = {Larry J. Stockmeyer},
  title     = {The Polynomial-Time Hierarchy},
  journal   = {TCS},
  volume    = {3},
  number    = {1},
  year      = {1976}
}

@Misc{indexsize,
author = {Charles Levine},
title = {{TPC} Benchmarks},
howpublished = {{\sl http://research.microsoft.com\\
/en-us/um/people/gray/WICS\_99\_TP/22\_Levine.ppt}}
}

@Misc{joincost,
 author =        {{Stack Overflow}},
  title =        {{SQL}: Inner joining two massive tables},
  howpublished = {{\sl http://stackoverflow.com/questions/1750001/sql-inner-joining-two-massive-tables}}
}


@article{pvldb14-distributed,
 author = {Wenfei Fan and Xin Wang and Yinghui Wu},
 title = {Distributed graph simulation: Impossibility and possibility},
 journal = {PVLDB},
volume={7},
  number={12},
 year = {2014}
 }

@inproceedings{PODS16,
  author = {Yang Cao and Wenfei Fan and Floris Geerts and Ping Lu},
  title =    {Bounded query rewriting using views},
 booktitle  =     {PODS},
  year = 2016
}

@article{GaasterlandL97,
  author    = {Terry Gaasterland and
               Jorge Lobo},
  title     = {Qualifying Answers According to User Needs and Preferences},
  journal   = {Fundam. Inform.},
  volume    = {32},
  number    = {2},
  year      = {1997},
  pages     = {121-137}
 }

@inproceedings{KadlagWFH04,
  author    = {Abhijit Kadlag and
               Amol V. Wanjari and
               Juliana Freire and
               Jayant R. Haritsa},
  title     = {Supporting Exploratory Queries in Databases},
  booktitle = {DASFAA},
  year      = {2004}
  }

@book{ER,
  author    = {Bernhard Thalheim},
  title     = {Entity-relationship modeling - foundations of database technology},
  publisher = {Springer},
  year      = {2000}
}

@book{DBcompletebook,
  author    = {Hector Garcia{-}Molina and
               Jeffrey D. Ullman and
               Jennifer Widom},
  title     = {Database systems - the complete book},
  publisher = {Pearson Education},
  year      = {2002}
}

@inproceedings{MWM,
  author    = {Harold N. Gabow},
  title     = {Data Structures for Weighted Matching and Nearest Common Ancestors
               with Linking},
  booktitle = {SODA},
  year      = {1990}
}

@Misc{Amazon-stat,
 author =        {Ina Steiner},
  title =        {How Many Products Does Amazon Actually Carry?},
  year = {2016},
  howpublished = {{\sl http://www.ecommercebytes.com/cab/abn/y16/m06/i17/s02}}
}


@article{mami2012survey,
  title={A survey of view selection methods},
  author={Mami, Imene and Bellahsene, Zohra},
  journal={SIGMOD Record},
  volume={41},
  number={1},
  pages={20--29},
  year={2012},
  publisher={ACM}
}

@inproceedings{chirkova2001formal,
  title={A formal perspective on the view selection problem},
  author={Chirkova, Rada and Halevy, Alon Y and Suciu, Dan},
  booktitle={VLDB},
   year={2001}
}

@inproceedings{yang1997framework,
  title={A framework for designing materialized views in data warehousing environment},
  author={Yang, Jian and Karlapalem, Kamalakar and Li, Qing},
  booktitle={ICDCS}, 
  pages={458--465},
  year={1997},
  organization={IEEE}
}

@inproceedings{gupta1997selection,
  title={Selection of views to materialize in a data warehouse},
  author={Gupta, Himanshu},
  booktitle={ICDT},
  pages={98--112},
  year={1997},
  organization={Springer}
}


@INPROCEEDINGS{fastfds,
  title={{FastFDs:} A heuristic{-}driven, depth{-}first algorithm for mining functional dependencies from relation instances extended abstract},
  author={Wyss, Catharine and Giannella, Chris and Robertson, Edward},
  booktitle={ DaWaK },
  year={2001},
}
@article{fan2011discovering,
  title={Discovering conditional functional dependencies},
  author={Fan, Wenfei and Geerts, Floris and Li, Jianzhong and Xiong, Ming},
  journal={TKDE},
  volume={23},
  number={5},
  pages={683--698},
  year={2011}
}

@inproceedings{renee,
author = {Fei Chiang and Renee Miller},
booktitle = {VLDB},
title = {Discovering Data Quality Rules},
  year      = {2008}
}
@article{discovery-DC,
  author    = {Xu Chu and
               Ihab F. Ilyas and
               Paolo Papotti},
  title     = {Discovering Denial Constraints},
  journal   = {{PVLDB}},
  volume    = {6},
  number    = {13},
  year      = {2013}
}

@article{DkS,
  title={Ruling out {PTAS} for graph min-bisection, dense k-subgraph, and bipartite clique},
  author={Khot, Subhash},
  journal={SICOMP},
  volume={36},
  number={4},
  year={2006}
}


@inproceedings{redbluecover,
  title={On the red-blue set cover problem},
  author={Carr, Robert D and Doddi, Srinivas and Konjevod, Goran and Marathe, Madhav V},
  booktitle={SODA},
  year={2000}
}

@inproceedings{EGDs,
  author    = {Catriel Beeri and
               Moshe Y. Vardi},
  title     = {The Implication Problem for Data Dependencies},
  booktitle = {Automata, Languages and Programming, 8th Colloquium, Acre (Akko),
               Israel, July 13-17, 1981, Proceedings},
  pages     = {73--85},
  year      = {1981}
}

@inproceedings{bauer2003solving,
  title={On solving the view selection problem in distributed data warehouse architectures},
  author={Bauer, Andreas and Lehner, Wolfgang},
  booktitle={SSDBM}, 
  pages={43--51},
  year={2003}
}

@inproceedings{gupta1999selection,
  title={Selection of views to materialize under a maintenance cost constraint},
  author={Gupta, Himanshu and Mumick, Inderpal Singh},
  booktitle={ICDT},
  year={1999}
  }
@inproceedings{mami2011modeling,
  title={Modeling view selection as a constraint satisfaction problem},
  author={Mami, Imene and Coletta, Remi and Bellahsene, Zohra},
  booktitle={DEXA},
  year={2011}
}
@article{lee2001speeding,
  title={Speeding up materialized view selection in data warehouses using a randomized algorithm},
  author={Lee, Minsoo and Hammer, Joachim},
  journal={IJCIS},
  volume={10},
  number={03},
  pages={327--353},
  year={2001}
}

@inproceedings{gupta1999maintenance,
  title={Maintenance of materialized views: problems, techniques, and applications},
  author={Gupta, Ashish and Mumick, Inderpal Singh},
  booktitle={Materialized views},
  pages={145--157},
  year={1999},
  organization={MIT Press}
}

@inproceedings{parQ-pattern,
  author    = {C{\'{e}}dric du Mouza and
               Philippe Rigaux and
               Michel Scholl},
  title     = {Efficient evaluation of parameterized pattern queries},
  booktitle = {CIKM},
  year      = {2005}
}
@inproceedings{parQ-stringgroupby,
  author    = {Luping Ding and
               Elke A. Rundensteiner},
  title     = {Index tuning for parameterized streaming groupby queries},
  booktitle = {SSPS},
  year      = {2008}
}
@inproceedings{parQ-DPlan,
  author    = {Ahmad Ghazal and
               Dawit Yimam Seid and
               Ramesh Bhashyam and
               Alain Crolotte and
               Manjula Koppuravuri and
               Vinod G},
  title     = {Dynamic plan generation for parameterized queries},
  booktitle = {SIGMOD},
  year      = {2009}
}

@inproceedings{parQ-skyline,
  author    = {Surajit Chaudhuri and
               Hongrae Lee and
               Vivek R. Narasayya},
  title     = {Variance aware optimization of parameterized queries},
  booktitle = {SIGMOD},
  year      = {2010}
}

@inproceedings{chirkova2002view,
  title={The view-selection problem has an exponential-time lower bound for conjunctive queries and views},
  author={Chirkova, Rada},
  booktitle={PODS},
  year={2002}
}


@article{VLDB17,
  author    = {Yang Cao and
               Wenfei Fan},
  title     = {Data Driven Approximation with Bounded Resources},
  journal   = {{PVLDB}},
  volume    = {10},
  number    = {9},
  pages     = {973--984},
  year      = {2017}
}

@inproceedings{BEAS,
  author    = {Yang Cao and
               Wenfei Fan and
               Yanghao Wang and
               Tengfei Yuan and
               Yanchao Li and
               Laura Yu Chen},
  title     = {{BEAS:} Bounded Evaluation of {SQL} Queries},
  booktitle = {SIGMOD},
  pages     = {1667--1670},
  year      = {2017}
}

@inproceedings{onlineML1,
  author    = {Thodoris Lykouris and
               Sergei Vassilvitskii},
  title     = {Competitive Caching with Machine Learned Advice},
  booktitle = {ICML},
  year      = {2018}
}
@inproceedings{onlineML2,
  author    = {Manish Purohit and
               Zoya Svitkina and
               Ravi Kumar},
  title     = {Improving Online Algorithms via {ML} Predictions},
  booktitle = {NeurIPS},
  year      = {2018}
}
@inproceedings{onlineML3,
  author    = {Michael Mitzenmacher},
  title     = {Scheduling with Predictions and the Price of Misprediction},
  journal   = {CoRR},
  volume    = {abs/1902.00732},
  year      = {2019},
  }

@inproceedings{cplex,
  title={Solving mixed-integer quadratic programming problems with {IBM-CPLEX}},
  author={Bliek1{\'u}, Christian and Bonami, Pierre and Lodi, Andrea},
  booktitle={RAMP},
  year={2014}
}

@Misc{gurobi,
 author =        {Gurobi Optimization, LLC.},
  title =        {Gurobi},
  year = {2019},
  howpublished = {{\sl http://www.gurobi.com}}
}

@book{ILPbook,
  title={Model building in mathematical programming},
  author={Williams, H Paul},
  year={2013},
  publisher={John Wiley \& Sons}
}
@article{DkSH,
  author    = {Benny Applebaum},
  title     = {Pseudorandom Generators with Long Stretch and Low Locality from Random
               Local One-Way Functions},
  journal   = {{SIAM} J. Comput.},
  volume    = {42},
  number    = {5},
  pages     = {2008--2037},
  year      = {2013}
}
@article{XpressMP,
  author    = {Robert Ashford},
  title     = {Mixed integer programming: {A} historical perspective with Xpress-MP},
  journal   = {Annals {OR}},
  volume    = {149},
  number    = {1},
  year      = {2007}
}

@misc{ILPstat,
author = {Amirhossein Moosavi},
year = {2017},
howpublished={\\{\sl{\url{https://www.researchgate.net/post/Why_the_CPLEX_solves_some_large-scale_insatnces_in_small_CPU_times}}}}
}

@article{competitive,
  author    = {Daniel Dominic Sleator and
               Robert Endre Tarjan},
  title     = {Amortized Efficiency of List Update and Paging Rules},
  journal   = {Commun. {ACM}},
  volume    = {28},
  number    = {2},
  pages     = {202--208},
  year      = {1985}
}

@book{onlinebook,
  author    = {Allan Borodin and
               Ran El{-}Yaniv},
  title     = {Online computation and competitive analysis},
  publisher = {Cambridge University Press},
  year      = {1998}
}

@article{paging1,
  author    = {Daniel Dominic Sleator and
               Robert Endre Tarjan},
  title     = {Amortized Efficiency of List Update and Paging Rules},
  journal   = {Commun. {ACM}},
  volume    = {28},
  number    = {2},
  pages     = {202--208},
  year      = {1985}
}

@article{cache1,
  author    = {Anna Adamaszek and
               Artur Czumaj and
               Matthias Englert and
               Harald R{\"{a}}cke},
  title     = {An \emph{O}(log \emph{k})-Competitive Algorithm for Generalized Caching},
  journal   = {{ACM} Trans. Algorithms},
  volume    = {15},
  number    = {1},
  year      = {2019}
}
@inproceedings{cache2,
  author    = {Sandy Irani},
  title     = {Page Replacement with Multi-Size Pages and Applications to Web Caching},
  booktitle = {STOC},
   year      = {1997}
}
@inproceedings{cache3,
  author    = {Guy Even and
               Moti Medina and
               Dror Rawitz},
  title     = {Online Generalized Caching with Varying Weights and Costs},
  booktitle = {SPAA},
  year      = {2018}
}
@article{cachefault,
  author    = {Marek Chrobak and
               Gerhard J. Woeginger and
               Kazuhisa Makino and
               Haifeng Xu},
  title     = {Caching Is Hard - Even in the Fault Model},
  journal   = {Algorithmica},
  volume    = {63},
  number    = {4},
  year      = {2012}
}
@inproceedings{indexad1,
  author    = {Gary Valentin and
               Michael Zuliani and
               Daniel C. Zilio and
               Guy M. Lohman and
               Alan Skelley},
  title     = {{DB2} Advisor: An Optimizer Smart Enough to Recommend Its Own Indexes},
  booktitle = {ICDE},
  year      = {2000}
}
@inproceedings{indexad2,
  author    = {Ivo Jimenez and
               Huascar Sanchez and
               Quoc Trung Tran and
               Neoklis Polyzotis},
  title     = {Kaizen: a semi-automatic index advisor},
  booktitle = {SIGMOD},
  year      = {2012}
}
@article{indexad3,
  author    = {Debabrata Dash and
               Neoklis Polyzotis and
               Anastasia Ailamaki},
  title     = {CoPhy: {A} Scalable, Portable, and Interactive Index Advisor for Large
               Workloads},
  journal   = {{PVLDB}},
  volume    = {4},
  number    = {6},
  year      = {2011}
}
@inproceedings{indexad4-,
  author    = {Rainer Schlosser and
               Jan Kossmann and
               Martin Boissier},
  title     = {Efficient Scalable Multi-attribute Index Selection Using Recursive
               Strategies},
  booktitle = {ICDE},
  year      = {2019}
}
@inproceedings{indexad5-,
  author    = {Himanshu Gupta and
               Venky Harinarayan and
               Anand Rajaraman and
               Jeffrey D. Ullman},
  title     = {Index Selection for {OLAP}},
  booktitle = {ICDE},
  year      = {1997}
}
@inproceedings{indexad6-,
  author    = {Karl Schnaitter and
               Neoklis Polyzotis},
  title     = {A Benchmark for Online Index Selection},
  booktitle = {ICDE},
  year      = {2009}
}
@inproceedings{indexad7-,
  author    = {Sanjay Agrawal and
               Surajit Chaudhuri and
               Vivek R. Narasayya},
  title     = {Automated Selection of Materialized Views and Indexes in {SQL} Databases},
  booktitle = {VLDB},
  year      = {2000}
}
@inproceedings{indexad8,
  author    = {Surajit Chaudhuri and
               Vivek R. Narasayya},
  title     = {An Efficient Cost-Driven Index Selection Tool for Microsoft {SQL}
               Server},
  booktitle = {VLDB},
  year      = {1997}
}
@inproceedings{indexad9,
  author    = {Adam Dziedzic and
               Jingjing Wang and
               Sudipto Das and
               Bolin Ding and
               Vivek R. Narasayya and
               Manoj Syamala},
  title     = {Columnstore and {B+} tree - Are Hybrid Physical Designs Important?},
  booktitle = {SIGMOD},
  year      = {2018}
}
@inproceedings{cracking1,
  author    = {Stratos Idreos and
               Martin L. Kersten and
               Stefan Manegold},
  title     = {Database Cracking},
  booktitle = {{CIDR}},
   year      = {2007}
}
@inproceedings{storage1,
  author    = {Michael F. Mitoma and
               Keki B. Irani},
  title     = {Automatic Data Base Schema Design and Optimization},
  booktitle = {VLDB},
  year      = {1975}
}
@article{cracking2,
  author    = {Felix Martin Schuhknecht and
               Alekh Jindal and
               Jens Dittrich},
  title     = {An experimental evaluation and analysis of database cracking},
  journal   = {{VLDB} J.},
  volume    = {25},
  number    = {1},
  year      = {2016}
}

@inproceedings{LRU,
  author    = {Elizabeth J. O'Neil and
               Patrick E. O'Neil and
               Gerhard Weikum},
  title     = {The {LRU-K} Page Replacement Algorithm For Database Disk Buffering},
  booktitle = {SIGMOD},
  year      = {1993}
}

@article{marker,
  author    = {Amos Fiat and
               Richard M. Karp and
               Michael Luby and
               Lyle A. McGeoch and
               Daniel Dominic Sleator and
               Neal E. Young},
  title     = {Competitive Paging Algorithms},
  journal   = {J. Algorithms},
  volume    = {12},
  number    = {4},
  year      = {1991}
}
@inproceedings{PLECO,
  author    = {Ashton Anderson and
               Ravi Kumar and
               Andrew Tomkins and
               Sergei Vassilvitskii},
  title     = {The dynamics of repeat consumption},
  booktitle = {WWW},
  year      = {2014}
}
@inproceedings{appro1,
  author    = {Surajit Chaudhuri and
               Bolin Ding and
               Srikanth Kandula},
  title     = {Approximate Query Processing: No Silver Bullet},
  booktitle = {SIGMOD},
  year      = {2017}
}
@inproceedings{sample1,
  author    = {Feifei Li and
               Bin Wu and
               Ke Yi and
               Zhuoyue Zhao},
  title     = {Wander Join: Online Aggregation for Joins},
  booktitle = {SIGMOD},
  year      = {2016}
}

@MISC{memcached,
  Title = {Memcached},
  note = {\url{http://memcached.org/}}
}

@MISC{rocksdb,
  Title = {RocksDB},
  note = {\url{https://rocksdb.org/}}
}

@article{VLDB19,
  author    = {Yang Cao and
               Wenfei Fan and
               Tengfei Yuan},
  title     = {Block as a Value for {SQL} over {NoSQL}},
  journal   = {{PVLDB}},
  volume    = {12},
  number    = {10},
  year      = {2019}
}

@article{paraQ1,
  author =       {P. Bizarro and N. Bruno and D.J. DeWitt},
  title =        {Progressive Parametric Query Optimization},
  journal =      {TKDE},
  volume =       21,
  number =       4,
  year =         2009
}

@inproceedings{paraQ2,
  author =       {Luping Ding and Elke A. Rundensteiner},
  title =        {Index tuning for parameterized streaming
                  groupby queries},
  booktitle =    {SSPS},
  year =         2008,
}

@inproceedings{paraQ3,
  author =       {Anshuman Dutt and Vivek Narasayya and Surajit
                  Chaudhuri},
  title =        {Leveraging Re-costing for Online Optimization
                  of Parameterized Queries with Guarantees},
  booktitle =    {SIGMOD},
  year =         2017,
}

@article{paraQ4,
  author =       {Immanuel Trummer and Christoph Koch},
  title =        {Multi-Objective Parametric Query Optimization},
  journal =      {The VLDB Journal},
  volume =       26,
  number =       1,
  year =         2016,
}
@inproceedings{paraQ5,
  author    = {Goetz Graefe and
               Karen Ward},
  title     = {Dynamic Query Evaluation Plans},
  booktitle = {SIGMOD},
  year      = {1989},
}
@inproceedings{paraQ6,
  author    = {Richard L. Cole and
               Goetz Graefe},
  title     = {Optimization of Dynamic Query Evaluation Plans},
  booktitle = {SIGMOD},
  year      = {1994},
}
@inproceedings{paraQ7,
  author    = {Antara Ghosh and
               Jignashu Parikh and
               Vibhuti S. Sengar and
               Jayant R. Haritsa},
  title     = {Plan Selection Based on Query Clustering},
  booktitle = {VLDB},
  year      = {2002},
}
@inproceedings{facebookmemcached,
  author    = {Rajesh Nishtala and
               Hans Fugal and
               Steven Grimm and
               Marc Kwiatkowski and
               Herman Lee and
               Harry C. Li and
               Ryan McElroy and
               Mike Paleczny and
               Daniel Peek and
               Paul Saab and
               David Stafford and
               Tony Tung and
               Venkateshwaran Venkataramani},
  title     = {Scaling Memcache at Facebook},
  booktitle = {NSDI},
  year      = {2013},
}
@inproceedings{lim2014mica,
  title={$\{$MICA$\}$: A Holistic Approach to Fast In-Memory Key-Value Storage},
  author={Lim, Hyeontaek and Han, Dongsu and Andersen, David G and Kaminsky, Michael},
  booktitle={NSDI},
  year={2014}
}
@inproceedings{ChalamalasettiLWARM13,
  author    = {Sai Rahul Chalamalasetti and
               Kevin T. Lim and
               Mitch Wright and
               Alvin AuYoung and
               Parthasarathy Ranganathan and
               Martin Margala},
  title     = {An {FPGA} memcached appliance},
  booktitle = {FPGA},
  year      = {2013}
}
@inproceedings{HetheringtonOA15,
  author    = {Tayler H. Hetherington and
               Mike O'Connor and
               Tor M. Aamodt},
  title     = {MemcachedGPU: scaling-up scale-out key-value stores},
  booktitle = {SoCC},
  year      = {2015}
}
@incollection{MorfoniosI18a,
  author    = {Konstantinos Morfonios and
               Yannis E. Ioannidis},
  title     = {Snowflake Schema},
  booktitle = {Encyclopedia of Database Systems, Second Edition},
  year      = {2018}
}
@inproceedings{DBLP:conf/vldb/BalkeG04,
  author    = {Wolf{-}Tilo Balke and
               Ulrich G{\"{u}}ntzer},
  title     = {Multi-objective Query Processing for Database Systems},
  booktitle = {VLDB},
  year      = {2004},
}
@article{DBLP:journals/jacm/BentleyKST78,
  author    = {Jon Louis Bentley and
               H. T. Kung and
               Mario Schkolnick and
               Clark D. Thompson},
  title     = {On the Average Number of Maxima in a Set of Vectors and Applications},
  journal   = {J. {ACM}},
  volume    = {25},
  number    = {4},
  year      = {1978}
}
@article{DBLP:journals/pvldb/LiuXPLZ15,
  author    = {Jinfei Liu and
               Li Xiong and
               Jian Pei and
               Jun Luo and
               Haoyu Zhang},
  title     = {Finding Pareto Optimal Groups: Group-based Skyline},
  journal   = {{PVLDB}},
  volume    = {8},
  number    = {13},
  year      = {2015}
}
@article{DBLP:journals/tkde/0004LHRD14,
  author    = {Nan Zhang and
               Chengkai Li and
               Naeemul Hassan and
               Sundaresan Rajasekaran and
               Gautam Das},
  title     = {On Skyline Groups},
  journal   = {{IEEE} Trans. Knowl. Data Eng.},
  volume    = {26},
  number    = {4},
  year      = {2014}
}
@article{regret,
  author    = {Danupon Nanongkai and
               Atish Das Sarma and
               Ashwin Lall and
               Richard J. Lipton and
               Jun (Jim) Xu},
  title     = {Regret-Minimizing Representative Databases},
  journal   = {Proc. {VLDB} Endow.},
  volume    = {3},
  number    = {1},
  year      = {2010}
}
@article{regret2,
  author    = {Min Xie and
               Raymond Chi{-}Wing Wong and
               Ashwin Lall},
  title     = {An experimental survey of regret minimization query and variants:
               bridging the best worlds between top-k query and skyline query},
  journal   = {{VLDB} J.},
  volume    = {29},
  number    = {1},
  year      = {2020}
}
@Misc{cassandra,
 author =        {},
  title =        {Cassandra Project},
  howpublished = {{\sl http://cassandra.apache.org/}}
}
@Misc{hive,
 author =        {},
  title =        {Apache Hive},
  howpublished = {{\sl https://hive.apache.org/}}
}
@Misc{phoenix,
 author =        {},
  title =        {Apache Phoenix},
  howpublished = {{\sl http://phoenix.apache.org/}}
}
@inproceedings{sparksql,
  author    = {Michael Armbrust and
               Reynold S. Xin and
               Cheng Lian and
               Yin Huai and
               Davies Liu and
               Joseph K. Bradley and
               Xiangrui Meng and
               Tomer Kaftan and
               Michael J. Franklin and
               Ali Ghodsi and
               Matei Zaharia},
  title     = {Spark {SQL:} Relational Data Processing in Spark},
  booktitle = {SIGMOD},
  year      = {2015}
}
@Misc{drill,
 author =        {},
  title =        {Apache Drill},
  howpublished = {{\sl https://drill.apache.org/}}
}
@Misc{impala,
 author =        {},
  title =        {Apache Impala},
  howpublished = {{\sl https://impala.apache.org/}}
}
@Misc{kudu,
 author =        {},
  title =        {Apache Kudu},
  howpublished = {{\sl https://kudu.apache.org/}}
}
@article{kvscan,
  author    = {Markus Pilman and
               Kevin Bocksrocker and
               Lucas Braun and
               Renato Marroquin and
               Donald Kossmann},
  title     = {Fast Scans on Key-Value Stores},
  journal   = {{PVLDB}},
  volume    = {10},
  number    = {11},
  year      = {2017}
}
@inproceedings{spanner,
  author    = {David F. Bacon and
               Nathan Bales and
               Nicolas Bruno and
               Brian F. Cooper and
               Adam Dickinson and
               Andrew Fikes and
               Campbell Fraser and
               Andrey Gubarev and
               Milind Joshi and
               Eugene Kogan and
               Alexander Lloyd and
               Sergey Melnik and
               Rajesh Rao and
               David Shue and
               Christopher Taylor and
               Marcel van der Holst and
               Dale Woodford},
  title     = {Spanner: Becoming a {SQL} System},
  booktitle = {SIGMOD},
  year      = {2017}
}
@article{spanner1,
  author    = {James C. Corbett and
               Jeffrey Dean and
               Michael Epstein and
               Andrew Fikes and
               Christopher Frost and
               J. J. Furman and
               Sanjay Ghemawat and
               Andrey Gubarev and
               Christopher Heiser and
               Peter Hochschild and
               Wilson C. Hsieh and
               Sebastian Kanthak and
               Eugene Kogan and
               Hongyi Li and
               Alexander Lloyd and
               Sergey Melnik and
               David Mwaura and
               David Nagle and
               Sean Quinlan and
               Rajesh Rao and
               Lindsay Rolig and
               Yasushi Saito and
               Michal Szymaniak and
               Christopher Taylor and
               Ruth Wang and
               Dale Woodford},
  title     = {Spanner: Google's Globally Distributed Database},
  journal   = {TODS},
  volume    = {31},
  number    = {3},
  year      = {2013}
}
@Misc{myrocks,
 author =        {Facebook},
  title =        {{MyRocks}},
  howpublished = {{{\sl https://code.facebook.com/posts/190251048047090/\\ myrocks-a-space-and-write-optimized-mysql-database/}}}
}
@inproceedings{AmazonKV,
  author    = {Giuseppe DeCandia and
               Deniz Hastorun and
               Madan Jampani and
               Gunavardhan Kakulapati and
               Avinash Lakshman and
               Alex Pilchin and
               Swaminathan Sivasubramanian and
               Peter Vosshall and
               Werner Vogels},
  title     = {Dynamo: Amazon's highly available key-value store},
  booktitle = {SOSP},
  year      = {2007}
}

@inproceedings{FacebookKV,
  author    = {Rajesh Nishtala and
               Hans Fugal and
               Steven Grimm and
               Marc Kwiatkowski and
               Herman Lee and
               Harry C. Li and
               Ryan McElroy and
               Mike Paleczny and
               Daniel Peek and
               Paul Saab and
               David Stafford and
               Tony Tung and
               Venkateshwaran Venkataramani},
  title     = {Scaling Memcache at {Facebook}},
  booktitle = {NSDI},
  year      = {2013}
}
@article{bigtable,
  author    = {Fay Chang and
               Jeffrey Dean and
               Sanjay Ghemawat and
               Wilson C. Hsieh and
               Deborah A. Wallach and
               Michael Burrows and
               Tushar Chandra and
               Andrew Fikes and
               Robert E. Gruber},
  title     = {Bigtable: A Distributed Storage System for Structured Data},
  journal   = {ACM Trans. Comput. Syst.},
  volume    = {26},
  number    = {2},
  year      = {2008}
  }
@Misc{hbase,
 author =        {Apache},
  title =        {HBase},
  howpublished = {{\sl https://hbase.apache.org/}}
}
@inproceedings{F1,
title = {F1: A Distributed {SQL} Database That Scales},
author  = {Jeff Shute and Radek Vingralek and Bart Samwel and Ben Handy and Chad Whipkey and Eric Rollins and Mircea Oancea and Kyle Littlefield and David Menestrina and Stephan Ellner and John Cieslewicz and Ian Rae and Traian Stancescu and Himani Apte},
year  = {2013},
booktitle = {PVLDB}
}
@article{NoSQLschema1, 
  author    = {Michael J. Mior and
               Kenneth Salem and
               Ashraf Aboulnaga and
               Rui Liu},
  title     = {{NoSE}: Schema Design for {NoSQL} Applications},
  journal   = {{IEEE} Trans. Knowl. Data Eng.},
  volume    = {29},
  number    = {10},
  year      = {2017}
}
@inproceedings{DBLP:conf/sigmod/Mior14,
  author    = {Michael J. Mior},
  editor    = {Pablo Barcel{\'{o}} and
               Lei Chen},
  title     = {Automated schema design for NoSQL databases},
  booktitle = {International Conference on Management of Data, {SIGMOD} 2014, Snowbird,
               Utah, USA, June 22, 2014, PhD Symposium},
  pages     = {41--45},
  publisher = {{ACM}},
  year      = {2014},
  url       = {https://doi.org/10.1145/2602622.2602624},
  doi       = {10.1145/2602622.2602624},
  timestamp = {Tue, 06 Nov 2018 11:07:38 +0100},
  biburl    = {https://dblp.org/rec/conf/sigmod/Mior14.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBSchema,
  author    = {Alexander Borgida and
               Marco A. Casanova and
               Alberto H. F. Laender},
  title     = {Logical Database Design: From Conceptual to Logical Schema},
  booktitle = {Encyclopedia of Database Systems, Second Edition},
  publisher = {Springer},
  year      = {2018}
}
@article{NoSQLschema2,
  author    = {Stefanie Scherzinger and
               Sebastian Sidortschuck},
  title     = {An Empirical Study on the Design and Evolution of {NoSQL} Database Schemas},
  journal   = {CoRR},
  volume    = {abs/2003.00054},
  year      = {2020},
}
@article{DBLP:journals/sigmod/MamiB12,
  author    = {Imene Mami and
               Zohra Bellahsene},
  title     = {A survey of view selection methods},
  journal   = {{SIGMOD} Rec.},
  volume    = {41},
  number    = {1},
  year      = {2012},
}
@MISC{greenplum,
  Title = {{Greenplum Database}},
  note = {{\sl https://greenplum.org/}}
}
@inproceedings{PapadomanolakisA07,
  author    = {Stratos Papadomanolakis and
               Anastassia Ailamaki},
  title     = {An Integer Linear Programming Approach to Database Design},
  booktitle = {ICDE Workshops},
  publisher = {{IEEE} Computer Society},
  year      = {2007},
}
@inproceedings{ChrysafisCDDEGG19,
  author    = {Christos Chrysafis and
               Ben Collins and
               Scott Dugas and
               Jay Dunkelberger and
               Moussa Ehsan and
               Scott Gray and
               Alec Grieser and
               Ori Herrnstadt and
               Kfir Lev{-}Ari and
               Tao Lin and
               Mike McMahon and
               Nicholas Schiefer and
               Alexander Shraer},
  title     = {{FoundationDB} Record Layer: {A} Multi-Tenant Structured Datastore},
  booktitle = {SIGMOD},
  pages     = {1787--1802},
  year      = {2019},
}
@inproceedings{QaderCH18,
  author    = {Mohiuddin Abdul Qader and
               Shiwen Cheng and
               Vagelis Hristidis},
  title     = {A Comparative Study of Secondary Indexing Techniques in LSM-based
               NoSQL Databases},
  booktitle = {SIGMOD},
  pages     = {551--566},
  year      = {2018}
}
@article{BrunoCKNRS11,
  author    = {Nicolas Bruno and
               Surajit Chaudhuri and
               Arnd Christian K{\"{o}}nig and
               Vivek R. Narasayya and
               Ravishankar Ramamurthy and
               Manoj Syamala},
  title     = {{AutoAdmin} Project at {Microsoft} Research: Lessons Learned},
  journal   = {{IEEE} Data Eng. Bull.},
  volume    = {34},
  number    = {4},
  pages     = {12--19},
  year      = {2011}
}
 @inproceedings{BrunoC05,
  author    = {Nicolas Bruno and
               Surajit Chaudhuri},
  editor    = {Fatma {\"{O}}zcan},
  title     = {Automatic Physical Database Tuning: {A} Relaxation-based Approach},
  booktitle = {SIGMOD},
  pages     = {227--238},
  year      = {2005}
}
@article{LeisGMBK015,
  author    = {Viktor Leis and
               Andrey Gubichev and
               Atanas Mirchev and
               Peter A. Boncz and
               Alfons Kemper and
               Thomas Neumann},
  title     = {How Good Are Query Optimizers, Really?},
  journal   = {Proc. {VLDB} Endow.},
  volume    = {9},
  number    = {3},
  pages     = {204--215},
  year      = {2015}
}
@MISC{imdbdata,
  Title = {{IMDB database}},
  note = {{\sl ftp://ftp.fu-berlin.de/pub/misc/movies/database/}}
}
@MISC{imdbquery,
  Title = {{IMDB benchmark queries}},
  note = {{\sl http://www-db.in.tum.de/~leis/qo/job.tgz}}
}