Encyclopedia of Database Systems. 2 Ed

Preface to the Second Edition....5 Preface to the First Edition....7 List of Topics....9 About the Editors....29 Advisory Board....31 Area Editors....39 List of Contributors....66 A....108 Absolute Time....108 Definition....108 Key Points....108 Cross-References....108 Recommended Reading....108 Abstract Versus Concrete Temporal Query Languages....109 Synonyms....109 Definition....109 Historical Background....109 Foundations....109 Abstract Temporal Query Languages....110 Multiple Temporal Dimensions and Complex Values....111 Concrete Temporal Query Languages....111 Compilation and Query Evaluation....112 Key Applications....113 Cross-References....113 Recommended Reading....114 Abstraction....114 Synonyms....114 Definition....114 Key Points....114 Cross-References....116 Recommended Reading....116 Access Control....116 Synonyms....116 Definition....116 Historical Background....116 Foundations....117 Key Applications....119 Future Directions....119 Cross-References....120 Recommended Reading....120 Access Control Administration Policies....121 Synonyms....121 Definition....121 Historical Background....121 Foundations....121 Key Applications....124 Cross-References....124 Recommended Reading....124 Access Control Policy Languages....124 Synonyms....124 Definition....124 Historical Background....125 Foundations....125 Key Applications....127 Future Directions....128 URL to Code....128 Cross-References....129 Recommended Reading....129 Access Path....129 Synonyms....129 Definition....129 Key Points....129 Cross-References....130 Recommended Reading....130 ACID Properties....130 Synonyms....130 Definition....130 Key Points....130 Cross-References....132 Recommended Reading....132 Active Database Coupling Modes....132 Definition....132 Historical Background....132 Foundations....132 Cross-References....133 Recommended Reading....134 Active Database Execution Model....134 Definition....134 Key Points....134 Cross-References....135 Recommended Reading....135 Active Database Knowledge Model....135 Definition....135 Key Points....135 Cross-References....136 Recommended Reading....136 Active Database Management System Architecture....136 Synonyms....136 Definition....136 Historical Background....136 Foundations....139 Key Applications....140 Future Directions....140 Cross-References....141 Recommended Reading....141 Active Database Rulebase....142 Definition....142 Key Points....142 Cross-References....142 Active Database, Active Database (Management) System....142 Definition....142 Historical Background....142 Foundations....143 Key Applications....143 Future Directions....143 Cross-References....144 Recommended Reading....144 Active Storage....144 Synonyms....144 Definition....145 Key Points....145 Cross-References....145 Recommended Reading....145 Active XML....145 Synonyms....145 Definition....146 Historical Background....146 Foundations....146 Key Applications....148 Cross-References....148 Recommended Reading....148 Active, Real-Time, and Intellective Data Warehousing....148 Synonyms....148 Definition....149 Historical Background....149 Foundations....151 Enabling Active Data Warehousing....151 Enabling Real-Time Data Warehousing....152 Key Applications....153 Future Directions....154 Cross-References....156 Recommended Reading....156 Activity....157 Synonyms....157 Definition....157 Key Points....157 Cross-References....158 Activity Diagrams....158 Synonyms....158 Definition....158 Historical Background....158 Scientific Fundamentals....159 Key Applications....162 Cross-References....162 Recommended Reading....162 Actors/Agents/Roles....163 Synonyms....163 Definition....163 Key Points....163 Cross-References....163 Adaptive Interfaces....163 Synonyms....163 Definition....163 Key Points....163 Cross-References....164 Adaptive Middleware for Message Queuing Systems....164 Synonyms....164 Definition....164 Historical Background....164 Foundations....165 Clustered Queues....165 Clustered Queue Performance....165 Provisioning....167 Control Rules for a Self-Optimizing Clustered Queue....167 Key Applications....168 Cross-References....168 Recommended Reading....168 Adaptive Query Processing....168 Synonyms....168 Definition....168 Key Points....168 Cross-References....169 Recommended Reading....170 Adaptive Stream Processing....170 Synonyms....170 Definition....170 Historical Background....170 Foundations....170 Minimizing Computation Cost....171 Eddies....171 Managing Resource Consumption....172 Load Shedding....172 Memory Minimization....173 Minimizing Communication....174 Key Applications....174 Future Directions....174 Cross-References....174 Recommended Reading....174 Administration Model for RBAC....175 Synonyms....175 Definition....175 Administrative RBAC....175 Scoped Administrative RBAC....175 Key Points....176 SARBAC....176 Cross-References....176 Recommended Reading....176 Administration Wizards....176 Definition....176 Historical Background....177 Foundations....177 Installation and Configuration....177 Data Import/Export....177 Back-Up/Restore....177 Key Applications....177 Recommended Reading....177 Advanced Information Retrieval Measures....177 Definition....177 Historical Background....178 More Graded Relevance Measures....178 Diversified Search Measures....178 Beyond Document Retrieval: Beyond Single Queries....178 Evaluating Evaluation Measures....179 Scientific Fundamentals....179 Key Applications....180 Future Directions....180 Data Sets....180 Cross-References....180 Recommended Reading....180 Aggregation: Expressiveness and Containment....181 Definition....181 Historical Background....181 Foundations....182 Expressiveness....182 Query Containment....183 Key Applications....185 Query Optimization....185 Query Rewriting....185 Future Directions....185 Cross-References....185 Recommended Reading....185 Aggregation-Based Structured Text Retrieval....186 Definition....186 Historical Background....186 Foundations....188 Aggregation-Based Approaches....191 Key Applications....193 Experimental Results....193 Data Sets....193 URL to Code....193 Cross-References....194 Recommended Reading....194 Air Indexes for Spatial Databases....194 Definition....194 Historical Background....195 Foundations....196 Key Applications....200 Location-Based Service....200 Moving Objects Monitoring....201 Cross-References....201 Recommended Reading....201 AJAX....201 Definition....201 Key Points....202 Cross-References....202 Recommended Reading....202 Allen's Relations....202 Synonyms....202 Definition....203 Key Points....203 Cross-References....204 Recommended Reading....204 α-nDCG....204 Synonyms....204 Definition....204 Main Text....204 Cross-References....205 AMOSQL....205 Definition....205 Key Points....205 Cross-References....205 Recommended Reading....206 AMS Sketch....206 Synonyms....206 Definition....206 Historical Background....206 Foundations....206 Problem Setup....206 Main Idea....207 Improving the Basic Schema....208 Key Applications....208 Experimental Results....208 URL to Code....209 Cross-References....209 Recommended Reading....209 Anchor Text....209 Synonyms....209 Definition....210 Key Points....210 Cross-References....210 Recommended Reading....210 Annotation....210 Definition....210 Key Points....210 Cross-References....211 Recommended Reading....211 Annotation-Based Image Retrieval....211 Synonyms....211 Definition....211 Historical Background....212 Foundations....212 Machine Learning Approaches....212 Relation Exploring Approaches....212 Semantic Template Approaches....213 Large-Scale Web Data-Supported Approaches....213 Key Applications....214 Cross-References....214 Recommended Readings....215 Anomaly Detection on Streams....215 Definition....215 Historical Background....215 Foundations....216 Outlier Detection....216 Clustering-Based and Forecasting-Based Approaches....216 Distribution-Based Approaches....216 Distance-Based and Density-Based Approaches....216 Change Detection....216 Streaming Algorithms....216 Sketching Techniques....217 Burst Detection....217 Correlation Analysis....217 Change Analysis....217 Key Applications....217 Intrusion Detection....217 System Monitoring....217 Process Control....217 Pervasive Healthcare....218 Civil Infrastructure....218 Future Directions....218 Cross-References....218 Recommended Reading....218 Anonymity....218 Synonyms....218 Definition....219 Key Points....219 Cross-References....219 Recommended Reading....219 ANSI/INCITS RBAC Standard....219 Synonyms....219 Definition....220 Key Points....221 Cross-References....221 Recommended Reading....221 Answering Queries Using Views....221 Synonyms....221 Definition....221 Historical Background....222 Foundations....222 Preliminaries....222 Conjunctive Queries....222 Views....222 Containment & Equivalence....222 Rewritings....223 Characterizing Rewritings....224 Techniques for Answering Queries Using Views....224 The Bucket Algorithm....224 The Inverse Rules Algorithm....225 The MiniCon Algorithm....225 Chase and Backchase....226 Key Applications....226 Future Directions....227 Cross-References....227 Recommended Reading....227 Anti-monotone Constraints....228 Synonyms....228 Definition....228 Key Points....228 Cross-References....228 Recommended Reading....228 Applicability Period....228 Definition....228 Key Points....229 Cross-References....229 Recommended Reading....229 Application Benchmark....229 Synonyms....229 Definition....229 Key Points....229 Cross-References....230 Recommended Reading....230 Application Recovery....230 Synonyms....230 Definition....230 Historical Background....230 Foundations....231 Introduction....231 Persisting Application State....231 Distributed Applications....232 Discussion....234 Key Applications....234 Cross-References....235 Recommended Reading....235 Application Server....235 Synonyms....235 Definition....235 Key Points....235 Cross-References....236 Recommended Reading....236 Application-Level Tuning....236 Synonyms....236 Definition....236 Historical Background....236 Foundations....236 Assemble Object Collections in Bulk....236 The Art of Insertion....237 Key Applications....238 Experimental Results....238 Looping Hurts....238 Url to Code and Data Sets....238 Cross-References....238 Recommended Reading....238 Applications of Emerging Patterns for Microarray Gene Expression Data Analysis....238 Definition....238 Key Points....239 Cross-References....239 Recommended Reading....239 Applications of Sensor Network Data Management....239 Synonyms....239 Definition....239 Historical Background....240 Foundations....240 Sensor Databases....240 Sensor Database Distinctions....240 Key Applications....241 Environmental Monitoring....241 Military Intelligence....241 Asset Management....242 Building Monitoring....242 Automotive....242 Healthcare....242 Industrial Monitoring....242 Future Directions....243 Data Sets....243 Cross-References....243 Recommended Reading....243 Approximate Queries in Peer-to-Peer Systems....244 Synonyms....244 Definition....244 Historical Background....244 Foundations....244 Approximation for Top-k Queries....244 Unstructured Networks....244 Hierarchical Networks....245 Structured Networks....245 Approximation for Aggregate Queries....245 Key Applications....246 Cross-References....246 Recommended Reading....246 Approximate Query Processing....246 Synonyms....246 Definition....247 Historical Background....247 Foundations....247 Pre-computed Synopsis....249 Online Query Processing....252 Key Applications....252 AQP in Relational Data Management....252 AQP in Spatial Data Management....252 AQP in Stream Data Management....252 AQP in Sensor Network....252 AQP in Semantic Web Search....253 Cross-References....253 Recommended Reading....253 Approximate Reasoning....253 Definition....253 Key Points....254 Cross-References....254 Recommended Reading....254 Approximation of Frequent Itemsets....254 Synonyms....254 Definition....254 Historical Background....254 Foundations....255 Noise-Tolerant Support Pruning....255 Experimental Results....257 Application....257 Cross-References....258 Recommended Reading....258 Apriori Property and Breadth-First Search Algorithms....259 Synonyms....259 Definition....259 Historical Background....259 Foundations....259 The Apriori Algorithm....260 Optimizations....260 Item Reordering....261 Partition....261 Sampling....261 Concise Representations....261 Key Applications....261 Experimental Results....262 Cross-References....262 Recommended Reading....262 Architecture-Conscious Database System....262 Synonyms....262 Definition....263 Historical Background....263 Foundations....263 Persistent Storage....263 Main Memory and Cache Optimizations....264 Microarchitecture Optimizations....264 On-Chip Parallelism....266 Key Applications....267 Future Directions....267 Cross-References....267 Recommended Reading....267 Archiving Experimental Data....268 Synonyms....268 Definition....268 Historical Background....268 Foundations....269 Key Applications....270 Future Directions....271 Cross-References....271 Recommended Reading....271 Armstrong Axioms....272 Definition....272 Key Points....272 Cross-References....272 Recommended Reading....272 Array Databases....272 Synonyms....272 Definition....272 Historical Background....272 Scientific Fundamentals....275 Algebraic Modeling....275 Array Query Languages....276 Physical Modeling....277 Query Evaluation....278 Query Optimization....278 Architecture....279 Key Applications....280 Earth Sciences....280 Life Science....280 Future Directions....281 Experimental Results....282 URL to Code....282 Cross-References....282 Recommended Reading....283 Association Rule Mining on Streams....284 Definition....284 Historical Background....284 Foundations....284 Two Subproblems....284 Key Challenges....285 Data Models....285 Algorithm Types....285 Representative Algorithms....286 Key Applications....287 Experimental Results....287 Data Sets....287 Cross-References....288 Recommended Reading....288 Association Rules....289 Definition....289 Historical Background....289 Foundations....289 Key Applications....290 Cross-References....290 Recommended Reading....290 Asymmetric Encryption....291 Synonyms....291 Definition....291 Key Points....291 Cross-References....291 Recommended Reading....292 Atelic Data....292 Synonyms....292 Definition....292 Key Points....292 Cross-References....293 Recommended Reading....293 Atomic Event....293 Synonyms....293 Definition....293 Key Points....293 Cross-References....293 Atomicity....293 Definition....293 Historical Background....294 Foundations....294 Future Directions....295 Cross-References....296 Recommended Reading....296 Audio....296 Synonyms....296 Definition....296 Historical Background....297 Foundations....297 Digital Audio....297 Audio Coding and Compression....297 Audio Content Analysis....298 Audio Retrieval....298 Key Applications....298 Cross-References....298 Recommended Reading....298 Audio Classification....299 Synonyms....299 Definition....299 Historical Background....299 Foundations....299 Key Audio Effect Detection....300 Classifier Learning....301 Probabilistic Inference....302 From Key Audio Effects to a Hierarchy of Semantic Concepts....303 Key Applications....305 Cross-References....305 Recommended Reading....305 Audio Content Analysis....305 Synonyms....305 Definition....306 Historical Background....306 Foundations....306 Key Applications....307 Cross-References....307 Recommended Reading....307 Audio Metadata....308 Synonyms....308 Definition....308 Historical Background....308 Foundations....310 Key Applications....312 Cross-References....312 Recommended Reading....312 Audio Representation....312 Synonyms....312 Definition....312 Historical Background....313 Foundations....313 Zero-Crossing Rate....313 Short Time Energy....314 Sub-band Energy Distribution....315 Brightness and Bandwidth....315 Mel-Frequency Cepstral Coefficient (MFCC)....315 Sub-band Partial Prominence and Harmonicity Prominence....315 High ZCR Ratio....316 Low Short-Time Energy Ratio....317 Spectrum Flux....318 Noise Frame Ratio....318 Feature Vector Generation....318 Key Applications....319 Cross-References....319 Recommended Reading....319 Audio Segmentation....320 Synonyms....320 Definition....320 Historical Background....320 Foundations....320 Audio Elements Detection and Weighting....321 Auditory Scene Segmentation....322 Key Applications....325 Cross-References....325 Recommended Reading....325 Auditing and Forensic Analysis....325 Synonyms....325 Definition....325 Historical Background....326 Foundations....326 Database Auditing....326 Database Forensics....328 Key Applications....330 Future Directions....330 Cross-References....330 Recommended Reading....330 Authentication....331 Definition....331 Historical Background....331 Foundations....331 Identification....331 Password-Based Authentication....332 Challenge-Response Identification....333 Data Origin Authentication....334 Key Applications....334 Cross-References....335 Recommended Reading....335 Automatic Image Annotation....335 Synonyms....335 Definition....335 Historical Background....335 Foundations....336 Images Description with Low-Level Features....337 Learning and Models....338 Current Results....341 Key Issues and Future Research....342 Key Applications....342 Cross-References....342 Recommended Reading....342 Autonomous Replication....343 Synonyms....343 Definition....343 Historical Background....343 Scientific Fundamentals....343 Common Architecture for Database Replica Provisioning....344 Overview of Dynamic Provisioning Solutions....345 Challenges for Database Replica Provisioning....346 Adaptation Delay....346 Oscillations in Allocation....346 Design Choices and Trade-Offs for Database Provisioning....346 Performance Modeling for Resource Allocation....347 Key Applications....347 Recommended Reading....347 Average Precision....348 Definition....348 Key Points....349 Cross-References....349 Average Precision at n....349 Synonyms....349 Definition....349 Key Points....349 Cross-References....350 Recommended Reading....350 Average Precision Histogram....350 Definition....350 Key Points....350 Cross-References....351 Recommended Reading....351 Average R-Precision....351 Definition....351 Key Points....351 Cross-References....352 Recommended Reading....352 B....353 B+-Tree....353 Synonyms....353 Definition....353 Historical Background....353 Foundations....353 Structure....353 Query Processing....354 Insertion....354 Deletion....355 Comparison with Some Other Index Structures....356 Key Applications....356 Future Directions....356 Cross-References....356 Recommended Reading....357 Backup and Restore....357 Synonyms....357 Definition....357 Key Points....357 Cross-References....357 Bag Semantics....358 Synonyms....358 Definition....358 Historical Background....358 Foundations....359 Key Applications....363 Future Directions....363 Recommended Reading....364 Bagging....364 Synonyms....364 Definition....364 Historical Background....365 Foundations....365 Key Applications....367 Future Directions....367 Cross-References....368 Recommended Reading....368 Bayesian Classification....369 Synonyms....369 Definition....369 Historical Background....369 Foundations....369 Key Applications....371 Text Document Classification....371 Image Pattern Recognition....371 Medical Diagnostic and Decision Support Systems....371 Email Spam Filtering....371 Data Sets....372 URL to Code....372 Cross-References....373 References....373 Benchmark Frameworks....373 Definition....373 URL to Code and Data Sets....374 Recommended Reading....374 Big Data Platforms for Data Analytics....374 Synonyms....374 Definition....374 Historical Background....374 Parallel Databases....374 Scalable Data Processing....375 Convergence....375 Scientific Fundamentals....375 System Layers....375 Influential Systems....376 Key Applications....378 Cross-References....378 Recommended Reading....378 Big Stream Systems....379 Synonyms....379 Definition....379 Historical Background....379 Scientific Fundamentals....380 Hadoop Online Prototype....380 Apache S4....380 Apache Storm....381 Spark Streaming....382 Key Applications....383 Cross-References....383 Recommended Reading....383 Biological Metadata Management....383 Definition....383 Historical Background....383 Foundations....384 Key Applications....386 Future Directions....387 Data Sets....387 URL to Code....388 Cross-References....388 Recommended Reading....388 Biological Networks....389 Synonyms....389 Definition....389 Key Points....389 Cross-References....389 Recommended Reading....389 Biological Resource Discovery....389 Definition....389 Historical Background....390 Foundations....390 Key Applications....391 Future Directions....392 Data Sets....392 URL to Code....392 Cross-References....393 Recommended Reading....393 Biological Sequences....393 Synonyms....393 Definition....393 Key Points....393 Cross-References....394 Recommended Reading....394 Biomedical Data/Content Acquisition, Curation....394 Synonyms....394 Definition....394 Historical Background....394 Foundations....395 Technical Issues....396 The Different Types of Expressivity of Ontologies/Vocabularies Used to Create the Annotations....396 Storage Schemes and Data Models to Store These Annotations in Underlying Databases....396 Techniques for Indexing the Curated Annotation for Retrieval....397 Workflow Aspects of the Curation Process....397 Key Applications....397 Future Directions....398 Cross-References....398 Recommended Reading....398 Biomedical Image Data Types and Processing....399 Synonyms....399 Definition....399 Historical Background....400 Foundations....400 Key Applications....402 Cross-References....403 Recommended Reading....403 Biomedical Scientific Textual Data Types and Processing....403 Synonyms....403 Definition....403 Historical Background....404 Foundations....405 Information Retrieval....405 Information Extraction....405 Text Mining....406 Key Applications....406 Cross-References....407 Recommended Reading....407 Biostatistics and Data Analysis....407 Definition....407 Historical Background....407 Foundations....408 Key Applications....409 Future Directions....410 Cross-References....410 Recommended Reading....410 Bitemporal Indexing....410 Synonyms....410 Definition....410 Historical Background....411 Foundations....411 Key Applications....414 Cross-References....414 Recommended Reading....415 Bitemporal Interval....415 Definition....415 Key Points....415 Cross-References....415 Recommended Reading....415 Bitemporal Relation....416 Synonyms....416 Definition....416 Key Points....416 Cross-References....416 Recommended Reading....416 Bitmap Index....417 Definition....417 Historical Background....417 Foundations....418 Key Applications....421 Future Directions....421 Cross-References....421 Recommended Reading....421 Bitmap-Based Index Structures....422 Synonyms....422 Definition....422 Historical Background....422 Foundations....422 Bitmap Encoding....422 Query Execution....423 Bitmap Compression....424 Key Applications....424 Cross-References....425 Recommended Reading....425 Blind Signatures....425 Definition....425 Key Points....426 Cross-References....426 Recommended Reading....426 Bloom Filters....426 Synonyms....426 Definition....426 Historical Background....427 Foundations....427 Key Applications....428 Future Directions....428 URL to Code....429 Cross-References....429 Recommended Reading....429 BM25....429 Synonyms....429 Definition....429 Historical Background....430 Foundations....430 Cross-References....431 Recommended Reading....432 Boolean Model....432 Definition....432 Historical Background....432 Foundations....433 Key Applications....436 Cross-References....436 Recommended Reading....437 Boosting....437 Definition....437 Historical Background....437 Foundations....438 Key Applications....440 Future Directions....440 Experimental Results....440 Cross-References....440 Recommended Reading....440 Bootstrap....441 Synonyms....441 Definition....441 Historical Background....441 Foundations....441 Key Applications....441 Cross-References....441 Recommended Reading....442 Boyce-Codd Normal Form....442 Synonyms....442 Definition....442 Key Points....442 Cross-References....442 Recommended Reading....442 BP-Completeness....443 Synonyms....443 Definition....443 Key Points....443 Cross-References....443 Recommended Reading....444 Bpref....444 Definition....444 Key Points....444 Cross-References....444 Recommended Reading....444 Browsing....444 Synonyms....444 Definition....445 Key Points....445 Cross-References....445 Recommended Reading....446 Browsing in Digital Libraries....446 Synonyms....446 Definition....446 Historical Background....446 Foundations....446 Key Applications....447 Future Directions....449 Experimental Results....449 Data Sets....449 Cross-References....449 Recommended Reading....449 B-Tree Locking....451 Synonyms....451 Definition....451 Historical Background....451 Foundations....452 Preliminaries....452 Two Forms of B-Tree Locking....452 Latch Coupling and Blink-Trees....453 Key Range Locking....454 Key Applications....455 Future Directions....455 URL to Code....456 Cross-References....456 Recommended Reading....456 Buffer Management....456 Definition....456 Historical Background....457 Scientific Fundamentals....457 The VM Approach....457 The Predictive Approach....458 The VM Versus the Predictive Approach....461 Key Applications....462 Cross-References....462 Recommended Reading....462 Buffer Manager....463 Synonyms....463 Definition....463 Historical Background....463 Foundations....463 Buffer Pool Interfaces....463 Replacement Policies....464 Asynchronous I/O....464 Concurrency Control and Recovery....464 Cooperative Buffer Pool Management....465 Key Applications....465 Future Directions....465 Cross-References....466 Recommended Reading....466 Buffer Pool....466 Synonyms....466 Definition....466 Historical Background....466 Foundations....467 Buffer Frames....467 Buffer Pool Data Structures....467 Replacement Policies....468 Key Applications....468 Future Directions....468 Cross-References....468 Recommended Reading....468 Business Intelligence....469 Definition....469 Historical Background....469 Scientific Fundamentals....469 Architectures....470 Functions....471 Methodologies....472 Tools....472 Key Applications....473 Future Directions....473 Cross-References....474 Recommended Reading....474 Business Process Execution Language....474 Synonyms....474 Definition....474 Key Points....475 Cross-References....475 Recommended Reading....475 Business Process Management....476 Synonyms....476 Definition....476 Historical Background....476 Foundations....477 Key Applications....479 Banking....479 Government....480 Business-to-Business....480 Health-Care....480 Cross-References....480 Recommended Reading....480 Business Process Modeling....480 Synonyms....480 Definition....480 Historical Background....481 Foundations....482 Scientific Fundamentals....485 Key Applications....486 Future Directions....486 Cross-References....487 Recommended Reading....487 Business Process Modeling Notation....488 Synonyms....488 Definition....488 Key Points....488 Cross-References....488 Recommended Reading....489 Business Process Reengineering....489 Synonyms....489 Definition....489 Historical Background....489 Foundations....490 Traditional Intra-organizational Reengineering....490 Supply Chain Management Process Reengineering....491 Knowledge Management Process Reengineering....492 Process Modeling Languages and Techniques....493 Key Applications....494 Cross-References....494 Recommended Reading....494 C....495 Cache-Conscious Query Processing....495 Synonyms....495 Definition....495 Historical Background....495 Scientific Fundamentals....495 Spatial Locality....496 Temporal Locality....496 Prefetching....497 Avoiding Cache Pollution and TLB Thrashing....498 Sampling....498 Key Applications....498 Future Directions....498 Cross-References....498 Recommended Reading....498 Calendar....499 Definition....499 Key Points....500 Cross-References....500 Recommended Reading....500 Calendric System....500 Definition....500 Key Points....500 Cross-References....501 Recommended Reading....501 CAP Theorem....501 Definition....501 Key Points....501 Recommended Reading....502 Cardinal Direction Relationships....502 Synonyms....502 Definition....502 Historical Background....502 Foundations....502 Key Applications....504 Future Directions....504 Cross-References....505 Recommended Reading....505 Cartesian Product....505 Synonyms....505 Definition....505 Key Points....505 Cross-References....506 Cataloging in Digital Libraries....506 Synonyms....506 Definition....506 Historical Background....506 Foundations....507 Classification....507 Cataloging....508 Key Applications....508 Dublin Core....511 XML....511 METS and MODS....511 Conclusion....511 Cross-References....512 Recommended Reading....512 Causal Consistency....512 Synonyms....512 Definition....513 Key Points....513 Historical Notes....514 Cross-References....514 Recommended Reading....514 Certain (and Possible) Answers....514 Synonyms....514 Definition....514 Key Points....515 Cross-References....516 Recommended Reading....516 Change Detection on Streams....517 Synonyms....517 Definition....517 Historical Background....517 Foundations....517 Regions of Interest....518 Estimating Probabilities....519 Statistical Testing....519 Key Applications....520 Future Directions....521 Cross-References....521 Recommended Reading....521 Channel-Based Publish/Subscribe....521 Synonyms....521 Definition....521 Key Points....521 Cross-References....523 Recommended Reading....523 Chart....523 Synonyms....523 Definition....523 Key Points....523 Cross-References....524 Recommended Reading....524 Chase....524 Definition....524 Comments....524 Historical Background....524 Foundations....525 Key Applications....527 Cross-References....528 Recommended Reading....528 Checksum and Cyclic Redundancy Check Mechanism....529 Synonyms....529 Definition....529 Key Points....529 Cross-References....530 Recommended Reading....530 Choreography....530 Definition....530 Key Points....530 Cross-References....531 Recommended Reading....531 Chronon....531 Synonyms....531 Definition....531 Key Points....531 Cross-References....531 Recommended Reading....531 Citation....531 Synonyms....531 Definition....532 Key Points....532 Cross-References....532 Recommended Reading....532 Classification....532 Synonyms....532 Definition....533 Historical Background....533 Foundations....534 Rules Based on a Single Attribute....534 Statistical Modeling (See Entry Bayesian Classification) ....534 Divide and Conquer Technique (See Entry Decision Tree Classification)....534 Covering Algorithms (See Entry Rule-Based Classification) ....535 Instance-Based Learning (See Entry Nearest Neighbor Classification) ....535 Linear Models (See Entry Linear Regression) ....535 Linear Classification (See Entry Neural Networks)....535 Missing Values....536 Meta-learning....536 Evaluation....536 Key Applications....537 URL to Code....537 Cross-References....537 Recommended Reading....537 Classification by Association Rule Analysis....538 Synonyms....538 Definition....538 Historical Background....538 Foundations....539 Classification Using Class Association Rules....539 Mining Class Association Rules for Classification....540 Classifier Building....540 Class Association Rules as Features....541 Classification Using Normal Association Rules....541 Key Applications....542 Cross-References....543 Recommended Reading....543 Classification in Streams....543 Synonyms....543 Definition....543 Historical Background....544 Foundations....544 Key Applications....545 Cross-References....545 Recommended Reading....545 Client-Server Architecture....545 Definition....545 Historical Background....546 Foundations....546 Key Applications....547 Cross-References....547 Recommended Reading....547 Clinical Data Acquisition, Storage, and Management....548 Synonyms....548 Definition....548 Historical Background....548 Foundations....549 Electronic Data Capture....549 Infrastructure and Standards for Data Exchange....549 Document Models and Management Systems....549 Common Components of Information Systems....550 Text-Oriented Information Systems....550 Key Applications....550 Electronic Data Collection Options....550 Patient Registries....550 Clinical Workflow Management....550 Quality Management, Report Generation, and Analysis....551 Future Directions....551 Cross-References....552 Recommended Reading....552 Clinical Data and Information Models....552 Definition....552 Key Points....552 Recommended Reading....553 Clinical Data Quality and Validation....553 Definition....553 Key Points....554 Accuracy....554 Completeness....554 Reliability....554 Cross-References....555 Recommended Reading....555 Clinical Decision Support....555 Synonyms....555 Definition....555 Historical Background....555 Foundations....556 Issues of Knowledge Representation....556 Storage of Clinical Knowledge in Database Systems....556 Standards for Sharing Clinical Decision Support Content Between Database Systems....557 Key Applications....557 Experimental Results....557 Cross-References....558 Recommended Reading....558 Clinical Document Architecture....558 Synonyms....558 Definition....559 Key Points....559 Cross-References....559 Recommended Reading....560 Clinical Event....560 Definition....560 Vernacular Definition....560 Technical Definitions....560 Key Points....560 Cross-References....561 Recommended Reading....561 Clinical Knowledge Repository....561 Synonyms....561 Definition....561 Key Points....561 Historical Background....562 Foundations....563 Key Applications....564 Cross-References....564 Recommended Reading....565 Clinical Observation....565 Synonyms....565 Definition....565 Key Points....565 Cross-References....566 Recommended Reading....566 Clinical Ontologies....566 Synonyms....566 Definition....566 Historical Background....566 Foundations....566 Properties of Clinical Ontologies....567 Key Applications....568 Prototypical Clinical Ontologies....568 Cross-References....569 Recommended Reading....569 Clinical Order....570 Synonyms....570 Definition....570 Key Points....570 Cross-References....571 Closed Itemset Mining and Nonredundant Association Rule Mining....571 Synonyms....571 Definition....571 Historical Background....571 Foundations....571 Mining Closed Frequent Itemsets....572 Non-redundant Association Rules....574 Key Applications....574 Future Directions....574 Experimental Results....574 Data Sets....574 Url to Code....574 Cross-References....574 Recommended Reading....574 Closest-Pair Query....575 Synonyms....575 Definition....575 Historical Background....575 Foundations....576 Key Applications....579 Geographical Information Systems....579 Data Analysis....580 Decision Making....580 Future Directions....580 Experimental Results....580 Data Sets....580 URL to Code....580 Cross-References....580 Recommended Reading....580 Cloud Computing....581 Definition....581 Historical Background....581 Scientific Fundamentals....582 Cloud Abstractions....582 Public and Private Clouds....583 Cloud Architectures....584 IaaS....584 PaaS....586 Data Center Maintenance and Power Optimization....586 Key Applications....587 Cross-References....587 Recommended Reading....587 Cloud Intelligence....587 Definition....587 Key Points....587 Cross-References....588 Recommended Reading....588 Cluster and Distance Measure....589 Synonyms....589 Definition....589 Clustering....589 Distance Measure....589 Key Points....589 Cross-References....590 Recommended Reading....590 Clustering for Post Hoc Information Retrieval....590 Synonyms....590 Definition....590 Historical Background....590 Scientific Fundamentals....591 Key Applications....592 Cross-References....594 Recommended Reading....594 Clustering on Streams....594 Definition....594 Historical Background....595 Foundations....595 Preliminaries....595 General Principles....596 Incremental Clustering....596 Representations....596 Hierarchical Clustering....597 On Relaxing the Number of Clusters....598 Clustering Evolving Data....598 Sliding Windows....598 Hierarchies of Windows....598 Decaying Data....599 Key Applications....599 Experimental Results....599 Cross-References....599 Recommended Reading....599 Clustering Overview and Applications....600 Synonyms....600 Definition....600 Historical Background....600 Foundations....600 The Clustering Process....600 Clustering Algorithms Taxonomy....601 Partitional Algorithms....602 Key Applications....603 Cross-References....604 Recommended Reading....605 Clustering Validity....605 Synonyms....605 Definition....605 Historical Background....606 Foundations....606 External Criteria....606 Comparison of C with Partition P (Non-hierarchical Clustering)....606 Internal Criteria....607 Validating Hierarchy of Clustering Schemes....607 Validating a Single Clustering Scheme....608 Relative Criteria....608 The Modified Hubert Γ Statistic....609 Dunn Family of Indices....609 RMSSDT, SPR, RS, CD....609 Key Applications....610 Cross-References....611 Recommended Reading....611 Clustering with Constraints....611 Synonyms....611 Definition....611 Historical Background....612 Foundations....613 Key Applications....615 URL to Code....615 Cross-References....615 Recommended Reading....615 Collaborative Filtering....615 Synonyms....615 Definition....616 Historical Background....616 Scientific Fundamentals....616 Item-Based Collaborative Filtering....616 User-Based Collaborative Filtering....617 Matrix Factorization....618 Key Applications....618 Recommendation....618 Personalized News Feed....618 Experimental Results....618 Data Sets....618 MovieLens....618 Netflix Prize....618 Yahoo! Music....618 URL to Code....619 LensKit....619 Apache Mahout....619 RecDB....619 Cross-References....619 Recommended Reading....619 Column Segmentation....619 Synonyms....619 Definition....619 Historical Background....620 Foundations....620 Challenges....621 Main Techniques....621 Rule-Based Systems....621 Hidden Markov Models....622 Conditional Models....622 Key Applications....623 URL to Code....623 Cross-References....624 Recommended Reading....624 Column Stores....624 Synonyms....624 Definition....624 Historical Background....624 Scientific Fundamentals....625 Key Applications....627 Cross-References....628 Recommended Reading....628 Common Warehouse Metamodel....629 Synonyms....629 Definition....629 Historical Background....629 Foundations....630 Object Model....630 Foundation....631 Resource....632 Analysis....632 Management....632 Key Applications....632 Cross-References....633 Recommended Reading....633 Comparative Visualization....633 Synonyms....633 Definition....633 Key Points....633 Cross-References....634 Recommended Reading....634 Compensating Transactions....634 Definition....634 Key Points....634 Cross-References....635 Recommended Reading....635 Complex Event....635 Synonyms....635 Definition....635 Key Points....635 Cross-References....635 Recommended Reading....635 Complex Event Processing....636 Synonyms....636 Definition....636 Key Points....636 Cross-References....637 Recommended Reading....637 Composite Event....637 Definition....637 Key Points....637 Cross-References....638 Recommended Reading....638 Composition....638 Synonyms....638 Definition....639 Key Points....639 Cross-References....639 Recommended Reading....639 Comprehensions....640 Synonyms....640 Definition....640 Key Points....640 Cross-References....640 Recommended Reading....641 Compression of Mobile Location Data....641 Synonyms....641 Definition....641 Historical Background....641 Scientific Fundamentals....643 Key Applications....648 Wireless Sensor Networks (WSN)....648 Location-Based Services (LBS)....648 Geographic Information Systems (GIS)....648 Spatiotemporal Data Mining....648 Future Directions....649 Cross-References....649 Recommended Reading....649 Computational Media Aesthetics....650 Synonyms....650 Definition....650 Historical Background....650 Foundations....651 Key Applications....652 Cross-References....652 Recommended Reading....652 Computationally Complete Relational Query Languages....653 Synonyms....653 Definition....653 Historical Background....653 Foundations....653 Key Applications....657 Future Directions....658 Cross-References....658 Recommended Reading....658 Computerized Physician Order Entry....659 Synonyms....659 Definition....659 Historical Background....659 Foundations....660 Technical Issues....662 Key Applications....664 Future Directions....664 Cross-References....664 Recommended Reading....664 Conceptual Modeling Foundations: The Notion of a Model in Conceptual Modeling....665 Synonyms....665 Definition....665 Main Text....665 Cross-References....667 Recommended Reading....667 Conceptual Schema Design....667 Definition....667 Historical Background....667 Foundations....668 Conceptual Schema Design in Practice....671 Key Applications....671 Future Directions....671 Cross-References....672 Recommended Reading....672 Concurrency Control for Replicated Databases....672 Synonyms....672 Definition....672 Historical Background....673 Scientific Fundamentals....673 Transactions in a Non-replicated System....673 Transaction Execution in a Replicated System....674 Execution Model and Architecture....674 Concurrency Control for One-Copy Serializability....675 Pessimistic Concurrency Control: Strict Two-Phase Locking....675 Principles....675 Architectural Comparison....676 Optimistic Concurrency Control....677 Concurrency Control for One-Copy Snapshot Isolation....678 Other Isolation Levels....678 Indirect Dependencies....678 Session Consistency....679 Summary....679 Experimental Results....680 Cross-References....680 Recommended Reading....680 Concurrency Control Manager....680 Synonyms....680 Definition....680 Key Points....681 Recommended Reading....681 Concurrency Control: Traditional Approaches....681 Synonyms....681 Definition....681 Key Points....682 Classification of Approaches....682 Cross-References....683 Recommended Reading....683 Conditional Tables....684 Synonyms....684 Definition....684 Key Points....684 Cross-References....685 Recommended Reading....685 Conjunctive Query....686 Synonyms....686 Definition....686 Key Points....686 Cross-References....687 Recommended Reading....687 Connection....687 Synonyms....687 Definition....687 Key Points....687 Cross-References....688 Recommended Reading....688 Consistency Models for Replicated Data....688 Synonyms....688 Definition....688 Historical Background....688 Foundations....688 Key Applications....689 Future Directions....690 Cross-References....690 Recommended Reading....690 Consistent Query Answering....690 Definition....690 Key Points....690 Cross-References....691 Recommended Reading....691 Constraint Databases....691 Definition....691 Key Points....691 Cross-References....692 Recommended Reading....692 Constraint Query Languages....692 Definition....692 Historical Background....693 Foundations....693 Key Applications....696 Cross-References....697 Recommended Reading....697 Constraint-Driven Database Repair....697 Synonyms....697 Definition....697 Historical Background....697 Foundations....698 Integrity Constraints for Characterizing Data Consistency....698 Repair Models....700 Methods for Finding Database Repairs....701 Key Applications....703 Future Directions....703 Cross-References....703 Recommended Reading....703 Content-and-Structure Query....704 Synonyms....704 Definition....704 Key Points....704 Cross-References....705 Recommended Reading....705 Content-Based Publish/Subscribe....705 Definition....705 Key Points....705 Cross-References....707 Recommended Reading....707 Content-Based Video Retrieval....707 Synonyms....707 Definition....707 Historical Background....708 Foundations....708 Unit of Retrieval....708 Representing Video Content Visually on Screen....709 Searching Archives of Digital Video....709 Content-Based Retrieval using Text Sources....710 Content-Based Retrieval using Visual Sources....710 Content-Based Retrieval using Audio Sources....711 Effective Retrieval....711 Key Applications....711 Future Directions....712 Experimental Results....712 Data Sets....714 Cross-References....714 Recommended Reading....715 Content-Only Query....715 Synonyms....715 Definition....715 Key Points....715 Cross-References....715 References....715 Context....716 Synonyms....716 Definition....716 Key Points....716 Cross-References....716 Recommended Reading....716 Contextualization in Structured Text Retrieval....717 Definition....717 Historical Background....717 Foundations....717 Key Applications....718 Experimental Results....718 Cross-References....719 Recommended Reading....719 Continuous Data Protection....719 Synonyms....719 Definition....719 Key Points....719 Cross-References....720 Recommended Reading....720 Continuous Monitoring of Spatial Queries....720 Synonyms....720 Definition....720 Historical Background....720 Foundations....720 Key Applications....725 Location-Based Services....725 Traffic Monitoring....725 Security Systems....725 Future Directions....725 Experimental Results....725 Cross-References....725 Recommended Reading....725 Continuous Multimedia Data Retrieval....726 Definition....726 Historical Background....726 Foundations....727 Retrieval of a Single Stream on a Single Disk....727 Retrieval of a Single Stream on Multiple Disks....727 Retrieval of Multiple Streams on a Single Disk....728 Retrieval of Multiple Streams on Multiple Disks....729 Key Applications....730 Cross-References....730 Recommended Reading....730 Continuous Queries in Sensor Networks....731 Synonyms....731 Definition....731 Historical Background....731 Foundations....732 Sensor Data Model....733 Continuous Query Models....733 Common Types of Continuous Queries in Sensor Networks Select-All Queries....734 Aggregate Queries....734 Join Queries....735 Key Applications....735 Habitat Monitoring....735 The Intelligent Building....735 Industrial Process Control....735 Cross-References....735 Recommended Reading....735 Continuous Query....736 Synonyms....736 Definition....736 Key Points....736 Cross-References....737 Recommended Reading....737 ConTract....737 Definition....737 Key Points....737 Cross-References....737 Recommended Reading....737 Control Data....738 Synonyms....738 Definition....738 Key Points....738 Cross-References....738 Convertible Constraints....738 Synonyms....738 Definition....738 Key Points....738 Cross-References....739 Recommended Reading....739 Coordination....739 Definition....739 Key Points....739 Cross-References....739 Recommended Reading....739 Copyright Issues in Databases....740 Synonyms....740 Definition....740 Historical Background....740 Foundations....740 Copyright....740 Standards for Obtaining Copyright....740 Originality....740 Fixation....741 The Duration of Copyright....741 Ownership and Transfer of Copyright....741 The Copyright Owner's Rights....741 Reproduction....742 Public Distribution, Performance, Display or Communication....742 Right of Adaptation, Modification or Right to Prepare Derivative Works....742 Theories of Secondary Liability....742 Contributory Infringement....742 Vicarious Liability for Copyright Infringement....742 Limitations and Exceptions....743 Remedies and Penalties....743 Key Applications....743 Cross-References....744 Recommended Reading....744 CORBA....744 Synonyms....744 Definition....744 Key Points....745 Cross-References....745 Recommended Reading....745 Correctness Criteria Beyond Serializability....746 Synonyms....746 Definition....746 Historical Background....746 Foundations....747 Multiversion Serializability....747 Semantic Consistency....748 Predicatewise Serializability....749 Epsilon Serializability....749 Eventual Consistency....749 Quasi-Serializability....749 Two-Level Serializability....750 Key Applications....750 Future Directions....750 Cross-References....751 Recommended Reading....751 Cost and Quality Trade-Offs in Crowdsourcing....751 Synonyms....751 Definition....751 Historical Background....752 Scientific Fundamentals....752 Future Directions....753 Recommended Reading....753 Cost Estimation....753 Definition....753 Historical Background....754 Foundations....755 Cost Components....755 Logical Costs/Data Volume....755 Algorithmic Costs/Complexity....755 Physical Costs/Execution Time....756 Cost Factors....756 Temporal Cost Factors....756 Spatial Cost Factors....757 Types of (Cost) Models....757 Architecture and Evaluation of Database Cost Models....758 Cross-References....758 Recommended Reading....758 Count-Min Sketch....759 Synonyms....759 Definition....759 Historical Background....759 Foundations....760 Update Procedure....760 Point Queries....760 Range, Heavy Hitter, and Quantile Queries....761 Inner Product Queries....762 Interpretation as Random Linear Projection....762 Conservative Update....762 Key Applications....762 Future Directions....763 Experimental Results....764 URL to Code....764 Cross-References....764 Recommended Reading....764 Coupling and Decoupling....765 Definition....765 Key Points....765 Cross-References....765 Covering Index....765 Definition....765 Key Points....766 Recommended Reading....766 Crash Recovery....766 Synonyms....766 Definition....766 Historical Background....766 Foundations....767 Consistency Concerns....767 Forward Recovery....768 Logging Methods and Rules....768 Taxonomy of Crash Recovery Algorithms....769 Implementation Implications....770 Archive Recovery....771 Key Applications....771 Future Directions....771 Cross-References....772 Recommended Reading....772 Cross-Language Mining and Retrieval....773 Synonyms....773 Definition....773 Historical Background....773 Foundations....774 Cross-Language Web Mining....774 Mining Parallel Data....774 Mining OOV Term Translation....774 Query Translation Disambiguation....775 Disambiguation by Term Similarity....775 Disambiguation by Term Co-occurrence....775 Disambiguation by Language Modeling....775 Pre-/Post-Translation Expansion....776 Cross-Lingual Query Suggestion....776 Latent Semantic Index (LSI) for CLIR....777 Key Applications....777 Experimental Results....777 Data Sets....777 Cross-References....777 Recommended Reading....778 Cross-Modal Multimedia Information Retrieval....778 Synonyms....778 Definition....779 Historical Background....779 Retrieval Approaches on Single-Modality....779 Retrieval Approaches on Multi-Modality Integration....779 Foundations....779 Layered Graph Model....780 Link Analysis Based Retrieval....781 Key Applications....781 Multimedia Information Retrieval System....781 Future Directions....782 Cross-References....783 Recommended Reading....783 Cross-Validation....783 Synonyms....783 Definition....784 Historical Background....784 Foundations....785 Resubstitution Validation....785 Hold-Out Validation....785 K-Fold Cross-Validation....785 Leave-One-Out Cross-Validation....785 Repeated K-Fold Cross-Validation....786 Pros and Cons....786 Why Tenfold Cross-Validation: From Ideal to Reality....786 Key Applications....788 Performance Estimation....788 Model Selection....788 Tuning....789 Cross-References....789 Recommended Reading....789 Crowd Database Operators....790 Synonyms....790 Definition....790 Historical Background....790 Scientific Fundamentals....790 Filtering Operators....790 Sorting, Top-k, and MAX Operators....791 Group-by Operators....793 Join Operators....793 Scan Operators....794 Key Applications....794 Crowd Database Systems....794 Users and Developers of Crowdsourcing Applications....794 Cross-References....795 Recommended Reading....795 Crowd Database Systems....795 Synonyms....795 Definition....795 Historical Background....796 Scientific Fundamentals....796 Architecture of Crowdsourcing Database Systems....796 Data Model and Query Language....796 Query Processing and Optimization....799 Key Applications....802 Cross-References....803 Recommended Reading....803 Crowd Mining and Analysis....804 Synonyms....804 Definition....804 Historical Background....804 Scientific Fundamentals....805 A Formal Model for the Crowd....805 Overall Significant Data Patterns....806 Exploring the Data Domain....806 Question Generation....806 Incorporating Existing Knowledge....806 Key Applications....807 Cross-References....807 Recommended Reading....807 Crowdsourcing Geographic Information Systems....808 Synonyms....808 Definition....808 Historical Background....808 Scientific Fundamentals....809 Key Applications....814 Mapping....814 Understanding Urban Form and Function....814 Traffic Assessment....814 3D Scene Reconstruction....814 Cross-References....814 Recommended Reading....814 Cube....815 Synonyms....815 Definition....815 Key Points....815 Cross-References....816 Recommended Reading....816 Cube Implementations....816 Synonyms....816 Definition....816 Historical Background....817 Foundations....818 Subcube Selection....818 Cube Computation....819 Query Processing....820 Incremental Maintenance....821 Key Applications....821 Cross-References....821 Recommended Reading....821 Current Semantics....822 Synonyms....822 Definition....822 Main Text....822 Cross-References....823 Recommended Reading....823 Curse of Dimensionality....823 Synonyms....823 Definition....823 Key Points....824 Cross-References....824 Recommended Reading....824 D....825 Daplex....825 Definition....825 Key Points....825 Cross-References....826 Recommended Reading....826 Data Acquisition and Dissemination in Sensor Networks....826 Synonyms....826 Definition....826 Historical Background....826 Foundations....827 Key Applications....830 Cross-References....830 Recommended Reading....830 Data Aggregation in Sensor Networks....831 Definition....831 Historical Background....831 Foundations....832 Approximate Aggregation....833 Duplicate-Insensitive Aggregation....834 Temporal Aspects of Aggregation....834 Other Aspects of Aggregation in Sensor Networks....835 Key Applications....836 Cross-References....836 Recommended Reading....836 Data Broadcasting, Caching, and Replication in Mobile Computing....837 Synonyms....837 Definition....837 Historical Background....837 Foundations....837 Data Broadcasting....837 Scheduling and Organization....838 Indexing....838 Data Caching and Replication....839 Key Applications....840 Cross-References....840 Recommended Reading....841 Data Center Energy Efficiency....841 Avoiding Waste in Current Systems....842 Greater Efficiency with Emerging Technologies....842 Improvements in Software and Algorithms....843 Recommended Reading....843 Data Cleaning....843 Definition....843 Historical Background....844 Foundations....844 Main Data Cleaning Tasks....844 Column Segmentation....844 Record Matching....844 Deduplication....845 Data Standardization....845 Data Profiling....845 Data Cleaning Platforms....845 Key Applications....846 Cross-References....846 Recommended Reading....846 Data Compression in Sensor Networks....847 Synonyms....847 Definition....847 Key Points....847 Cross-References....848 Recommended Reading....848 Data Conflicts....849 Synonyms....849 Definition....849 Historical Background....849 Foundations....849 Classification of Data Conflicts....849 Single-Source Data Conflicts....849 Multi-source Data Conflicts....850 Dealing with Data Conflicts....852 Key Applications....852 Data Warehousing....852 Data Mining....852 Cross-References....853 Recommended Reading....853 Data Definition....853 Synonyms....853 Definition....853 Historical Background....853 Scientific Fundamentals....853 Key Applications....854 Cross-References....854 Recommended Reading....854 Data Definition Language (DDL)....854 Synonyms....854 Definition....854 Historical Background....854 Scientific Fundamentals....855 Key Applications....855 Cross-References....855 Recommended Reading....855 Data Dictionary....855 Synonyms....855 Definition....855 Key Points....855 Cross-References....856 Recommended Reading....856 Data Encryption....856 Synonyms....856 Definition....857 Historical Background....857 Foundations....857 Stream Ciphers....857 Block Ciphers....858 Public Key Encryption Algorithms....859 Attack Models....859 Key Applications....859 Cross-References....859 Recommended Reading....859 Data Estimation in Sensor Networks....860 Synonyms....860 Definition....860 Key Points....860 Cross-References....860 Recommended Reading....861 Data Exchange....861 Synonyms....861 Definition....861 Historical Background....861 Foundations....862 Key Applications....868 Cross-References....868 Recommended Reading....868 Data Fusion....868 Synonyms....868 Definition....869 Historical Background....869 Scientific Fundamentals....870 Key Applications....872 Data Integration and Data Warehousing....872 Knowledge Base Construction and Knowledge Fusion....872 Future Directions....872 Experimental Results....873 Data Sets....873 Cross-References....873 Recommended Reading....873 Data Fusion in Sensor Networks....873 Synonyms....873 Definition....873 Historical Background....874 Foundations....874 Key Applications....877 Data Sets....877 Cross-References....877 Recommended Reading....877 Data Generation....878 Synonyms....878 Definition....878 Scientific Fundamentals....878 Key Applications....878 URL to Code and Data Sets....879 Cross-References....879 Recommended Reading....879 Data Integration Architectures and Methodology for the Life Sciences....879 Definition....879 Historical Background....879 Foundations....880 Key Applications....883 Future Directions....884 Cross-References....884 Recommended Reading....884 Data Integration in Web Data Extraction System....885 Synonyms....885 Definition....885 Historical Background....885 Foundations....886 Semi-structured Data....886 Schema and Instance Matching....886 Web Content Mining....887 Key Applications....887 Vertical Search....887 Web Intelligence....887 Situational Applications....888 Cross-References....888 Recommended Reading....888 Data Management for VANETs....888 Synonyms....888 Definition....889 Main Text....889 Cross-References....890 Recommended Reading....890 Data Management Fundamentals: Database Management System....890 Synonyms....890 Definition....890 Historical Background....890 Scientific Fundamentals....891 Key Applications....891 Cross-References....891 Recommended Reading....891 Data Management in Data Centers....892 Synonyms....892 Definition....892 Historical Background....892 Scientific Fundamentals....893 Key-Value Stores....893 Large-Scale Transactional Databases....894 Geo-replication and Distribution....896 Multi-tenancy....896 Future Directions....897 Cross-References....897 Recommended Reading....897 Data Manipulation Language (DML)....898 Synonyms....898 Definition....898 Historical Background....898 Scientific Fundamentals....898 Key Applications....898 Cross-References....898 Recommended Reading....899 Data Mart....899 Definition....899 Main Text....899 Cross-References....900 References....900 Data Migration Management....900 Synonyms....900 Definition....900 Historical Background....900 Scientific Fundamentals....901 Key Applications....903 Cross-References....903 Recommended Reading....903 Data Mining....903 Synonyms....903 Definition....903 Historical Background....904 Foundations....904 Mining Interesting Patterns from Massive Amount of Data....904 Scalable Classification and Predictive Modeling....904 Cluster and Outlier Analysis....905 Multidimensional (OLAP) Analysis....905 Mining Different Kinds of Data....905 Key Applications....905 Biological Data Mining....905 Data Mining for Software Engineering....906 Future Directions....906 Mining Information Networks....906 Invisible Data Mining....906 Privacy-Preserving Data Mining....906 Experimental Results....906 Data Sets....907 URL to Code....907 Cross-References....907 Recommended Reading....907 Data Partitioning....908 Definition....908 Key Points....908 Cross-References....909 Data Privacy and Patient Consent....909 Synonyms....909 Definition....909 Historical Background....909 Foundations....910 Key Applications....913 Electronic Health Records....913 Medical Research....913 Cross-References....913 Recommended Reading....913 Data Profiling....914 Synonyms....914 Definition....914 Historical Background....914 Foundations....914 Basic Statistics....914 Distributional Statistics....914 Textual Summaries....915 Structural Summaries....915 Samples....916 Implementation Considerations....916 Modes of Use....917 Key Applications....917 Cross-References....917 Recommended Reading....917 Data Provenance....918 Synonyms....918 Definition....918 Key Points....918 Cross-References....918 Recommended Reading....918 Data Quality Assessment....918 Synonyms....918 Definition....919 Historical Background....919 Foundations....919 Key Applications....922 Future Directions....922 Cross-References....922 Recommended Reading....922 Data Quality Dimensions....923 Synonyms....923 Definition....923 Historical Background....923 Foundations....923 Classifications....923 Completeness....924 Accuracy....925 Consistency....925 Timeliness....926 Further Dimensions....926 Key Applications....926 Cross-References....926 Recommended Reading....926 Data Quality Models....927 Synonyms....927 Definition....927 Historical Background....927 Foundations....928 Key Applications....931 Future Directions....931 Cross-References....932 Recommended Reading....932 Data Rank/Swapping....932 Synonyms....932 Definition....932 Key Points....932 Cross-References....933 Recommended Reading....933 Data Reduction....933 Definition....933 Historical Background....933 Foundations....934 Histograms....935 Clustering....936 Singular Value Decomposition (SVD)....936 Discrete Wavelet Transform (DWT)....937 Key Applications....938 Data Storage and Transfer....938 Database Management Systems....938 OLAP....938 Multimedia Data....938 Taxonomy....938 Cross-References....938 Recommended Reading....938 Data Replication....939 Synonyms....939 Definition....939 Historical Background....939 Scientific Fundamentals....940 Replica Control....940 Replica Control and Concurrency Control....941 Weak Consistency Models and Conflict Resolution....942 Availability....942 Replica Allocation....943 Replication in Various Computing Environments....943 Key Applications....944 Future Directions....944 Cross-References....945 Recommended Reading....945 Data Sampling....946 Definition....946 Historical Background....946 Foundations....946 Key Applications....949 Query Optimization....949 Approximate Query Processing....949 Data Streaming....949 Cross-References....949 Recommended Reading....949 Data Scrubbing....950 Synonyms....950 Definition....950 Historical Background....950 Scientific Fundamentals....951 Key Applications....953 Future Directions....953 Cross-References....954 Recommended Reading....954 Data Sketch/Synopsis....954 Synonyms....954 Definition....954 Key Points....954 Cross-References....955 Recommended Reading....955 Data Skew....955 Synonyms....955 Definition....955 Key Points....955 Cross-References....955 Recommended Reading....955 Data Storage and Indexing in Sensor Networks....956 Definition....956 Historical Background....956 Foundations....956 Key Applications....958 Cross-References....958 Recommended Reading....958 Data Stream....959 Synonyms....959 Definition....959 Key Points....959 Cross-References....960 Recommended Reading....960 Data Stream Management Architectures and Prototypes....960 Definition....960 Historical Background....960 Foundations....960 Prototypes....962 Key Applications....965 URL to Code....965 Cross-References....965 Recommended Reading....965 Data Types in Scientific Data Management....966 Synonyms....966 Definition....966 Foundations....966 Commonly Used Data Types in Science Applications....966 Arrays....966 Time-Series....967 Finite Element Meshes....967 Graphs....967 Some Basic Issues About Scientific Data Types....968 Key Applications....969 Cross-References....969 Recommended Reading....969 Data Uncertainty Management in Sensor Networks....969 Synonyms....969 Definition....969 Historical Background....970 Foundations....970 Modeling Uncertainty....970 Queries....971 Implementation....972 Indexing....973 Key Applications....973 Future Directions....973 Cross-References....974 Recommended Reading....974 Data Visualization....975 Synonyms....975 Definition....975 Historical Background....975 Foundations....978 Key Applications....980 Statistics....980 Information Systems....980 Documentation....982 Computational Science....982 Cross-References....982 Recommended Reading....982 Data Warehouse....982 Synonyms....982 Definition....983 DW Environment and Model....983 Cross-References....983 Recommended Reading....984 Data Warehouse Life Cycle and Design....984 Synonyms....984 Definition....984 Historical Background....984 Foundations....985 Key Applications....989 Designers....989 Business Users....989 Future Directions....989 Cross-References....989 Recommended Reading....990 Data Warehouse Maintenance, Evolution, and Versioning....990 Synonyms....990 Definition....990 Historical Background....991 Scientific Fundamentals....991 Key Applications....995 Future Directions....995 Cross-References....996 Recommended Reading....996 Data Warehouse Metadata....997 Definition....997 Historical Background....997 Foundations....998 Key Applications....1002 Cross-References....1003 Recommended Reading....1003 Data Warehouse Security....1003 Synonyms....1003 Definition....1004 Historical Background....1004 Scientific Fundamentals....1005 Security in Data Sources....1005 Security in ETL Processes....1006 Security in Data Warehouses Modeling....1006 Security in OLAP Tools....1007 Key Applications....1008 Cross-References....1008 Recommended Reading....1008 Data Warehousing for Clinical Research....1009 Synonyms....1009 Definition....1009 Historical Background....1009 Foundations....1009 Database Design for Clinical Research Data Warehouse....1009 Metadata Management in Clinical Research Data Warehouse....1010 Privacy Management in the Clinical Research Data Warehouse....1012 Data Flow in Clinical Research Data Warehouse....1012 Key Applications....1012 Cross-References....1013 Recommended Reading....1013 Data Warehousing in Cloud Environments....1014 Synonyms....1014 Definition....1014 Historical Background....1014 Scientific Fundamentals....1015 Key Applications....1017 Future Directions*....1018 Experimental Results*....1018 URL to Code*....1018 Cross References....1018 Recommended Reading....1018 Data Warehousing on Nonconventional Data....1019 Definition....1019 Historical Background....1019 Scientific Fundamentals....1020 Key Applications....1021 Future Directions....1021 Cross-References....1021 Recommended Reading....1021 Data Warehousing Systems: Foundations and Architectures....1022 Definition....1022 Historical Background....1022 Scientific Fundamentals....1023 OLTP Versus Data Warehousing Systems....1023 ROLAP and MOLAP....1023 Data Warehousing Architecture....1025 Data Source Systems....1025 ETL Management Services....1026 Data Warehouse Storage and Metadata Repository....1027 Data Mart and OLAP Engines....1027 Front-End Tools....1027 Other DW Architectures....1027 Independent Data Marts Architecture....1028 Data Mart Bus Architecture with Conformed Dimensions....1028 Centralized Data Warehouse Architecture....1028 Hub-and-Spoke Architecture (Corporate Information Factory)....1028 Distributed Data Warehouse Architecture....1029 Federated Data Warehouse Architecture....1029 Virtual Data Mart Architecture....1030 Key Applications....1030 Future Direction....1030 URL to CODE....1031 Cross-References....1032 Recommended Reading....1032 Data, Text, and Web Mining in Healthcare....1033 Synonyms....1033 Definition....1033 Historical Background....1033 Foundations....1033 Data Mining....1033 Text Mining....1033 Web Mining....1034 Key Applications....1034 Data Mining in Healthcare....1034 Text Mining in Healthcare....1034 Web Usage Mining in Healthcare....1035 Experimental Results....1035 Cross-References....1036 Recommended Reading....1036 Database....1037 Definition....1037 Historical Background....1037 Key Applications....1037 Cross-References....1037 Recommended Reading....1038 Database Adapter and Connector....1038 Synonyms....1038 Definition....1038 Historical Background....1038 Foundations....1038 Key Applications....1041 URL To Code....1041 Cross-References....1041 Recommended Reading....1041 Database Administrator (DBA)....1041 Definition....1041 Historical Background....1041 Key Applications....1042 Cross-References....1042 Recommended Reading....1042 Database Benchmarks....1042 Definition....1042 Historical Background....1042 Scientific Fundamentals....1043 Key Applications....1044 Experimental Results....1044 URL to Code and Data Sets....1044 Cross-References....1044 Recommended Reading....1044 Database Clustering Methods....1045 Synonyms....1045 Definitions....1045 Key Points....1045 Cross-References....1046 Recommended Reading....1046 Database Clusters....1046 Synonyms....1046 Definition....1046 Historical Background....1047 Foundations....1047 Key Applications....1048 Future Directions....1049 Experimental Results....1049 Data Sets....1050 URL to Code....1050 Cross-References....1050 Recommended Reading....1050 Database Dependencies....1051 Synonyms....1051 Definition....1051 Historical Background....1051 Foundations....1052 Inference....1052 Decompositions....1054 Key Applications....1055 Cross-References....1055 Recommended Reading....1055 Database Design....1056 Definition....1056 Key Points....1056 Cross-References....1057 Recommended Reading....1057 Database Languages for Sensor Networks....1057 Synonyms....1057 Definition....1058 Historical Background....1058 Foundations....1059 Restricted Expressiveness....1059 Specialized Language Constructs....1061 Key Applications....1061 Cross-References....1061 Recommended Reading....1061 Database Machine....1062 Definition....1062 Key Points....1062 Cross-References....1063 Recommended Reading....1063 Database Management System....1063 Synonyms....1063 Definition....1063 Historical Background....1063 Foundations....1064 Key Applications....1067 Cross-References....1067 Recommended Reading....1068 Database Middleware....1068 Synonyms....1068 Definition....1068 Historical Background....1068 Foundations....1069 Database Middleware for Integration....1069 Database Middleware for Scaling and Availability....1069 Transactional and Messaging Middleware....1070 Middleware for Adaptation and Reconfiguration....1071 Key Applications....1071 Cross-References....1071 Recommended Reading....1071 Database Repair....1072 Definition....1072 Key Points....1072 Cross-References....1072 Recommended Reading....1072 Database Reverse Engineering....1073 Synonyms....1073 Definition....1073 Historical Background....1073 Foundations....1073 Database Design Revisited....1074 Standard Database Design Methodology....1074 Empirical Database Design....1074 Database Reverse Engineering Processes....1075 Physical Schema Extraction....1075 Logical Schema Reconstruction....1076 Implicit Constructs....1076 Sources and Techniques....1076 Schema Conceptualization....1077 Tools....1078 Examples....1078 Key Applications....1078 Cross-References....1078 Recommended Reading....1078 Database Schema....1079 Synonyms....1079 Definition....1079 Historical Background....1079 Scientific Fundamentals....1079 Key Applications....1080 Cross-References....1080 Recommended Reading....1080 Database Security....1080 Synonyms....1080 Definition....1080 Historical Background....1080 Foundations....1081 Key Applications....1084 Cross-References....1084 Recommended Reading....1084 Database Techniques to Improve Scientific Simulations....1085 Synonyms....1085 Definition....1085 Historical Background....1085 Foundations....1086 Local Models....1086 ISAT Algorithm....1086 Indexing Problem....1087 Tuning Retrieves....1088 Tuning Grows and Adds....1088 An Example: Binary Tree....1089 Retrieve....1089 Update....1090 Long Running Simulations....1090 Key Applications....1090 Recommended Reading....1090 Database Trigger....1091 Synonyms....1091 Definition....1091 Key Points....1091 Cross-References....1091 Recommended Readings....1091 Database Tuning Using Combinatorial Search....1091 Definition....1091 Historical Background....1092 Foundations....1092 Example: Physical Database Design using Combinatorial Search....1092 Future Directions....1094 Cross-References....1094 Recommended Reading....1094 Database Tuning Using Online Algorithms....1095 Definition....1095 Historical Background....1095 Foundations....1096 Expanded Example: Self Tuning Histograms....1096 Future Directions....1098 Cross-References....1098 Recommended Reading....1098 Database Tuning Using Trade-Off Elimination....1099 Definition....1099 Historical Background....1099 Foundations....1099 Example: Cache Management with Trade-off Elimination....1100 Future Directions....1102 Cross-References....1102 Recommended Reading....1102 Database Use in Science Applications....1103 Definition....1103 The Problem....1103 Foundations....1103 Key Applications....1106 Cross-References....1106 Recommended Reading....1106 Datalog....1106 Synonyms....1106 Definition....1106 Historical Background....1107 Foundations....1107 Datalog Syntax....1107 Definition 1....1107 Semantics....1107 Evaluation and Optimization of Datalog....1109 Datalog with Negation....1110 Key Applications....1110 Current and Potential Users and the Motivation of Studying This Area....1110 Cross-References....1110 Recommended Reading....1110 DBMS Component....1111 Synonyms....1111 Definition....1111 Key Points....1111 Cross-References....1111 Recommended Reading....1111 DBMS Interface....1111 Synonyms....1111 Definition....1111 Key Points....1112 Cross-References....1112 Recommended Reading....1112 DCE....1112 Synonyms....1112 Definition....1112 Key Points....1112 Cross-References....1113 Recommended Reading....1113 DCOM....1113 Synonyms....1113 Definition....1113 Key Points....1113 Cross-References....1114 Recommended Reading....1114 Decay Models....1114 Definition....1114 Historical Background....1115 Kernel Estimation....1115 Time-Decay....1115 Network....1115 Euclidean Plane....1116 Foundations....1116 Metric Space....1116 Decay Functions....1116 Aggregate Functions....1116 Computational Challenges....1117 All Distances Sketches....1117 Key Applications....1117 Cross-References....1117 Recommended Reading....1118 Decision Rule Mining in Rough Set Theory....1118 Synonyms....1118 Definition of the Subject....1118 Historical Background....1119 Scientific Fundamentals....1119 Attribute(Column) Reducts and Candidate Keys....1119 Value Reducts: Simplest Decision Rules....1120 Illustration....1120 Select a Decision Table....1120 Step 1: Split the Decision Table....1120 Step 2: Find the Decision Classes in Consistent Table....1120 Step 3: Find the Condition Classes in Consistent Table....1120 Step 4: Observe the Knowledge Dependencies....1120 Step 5: Organizing into ``If-Then'' Rules....1121 Step 6: Attribute (Column) Reducts....1121 Step 7: Drop the Repeated Tuples....1121 Step 8: Value Reducts....1121 Extended RDB Theories....1122 Graph RDB Theory....1123 Cross-References....1123 Recommended Reading....1123 Decision Tree Classification....1123 Synonyms....1123 Definition....1123 Historical Background....1124 Foundations....1124 Formal Definition....1124 Building Decision Tree Classifiers....1125 Split Attribute and Split Point Selection....1125 Tree Pruning....1127 Key Applications....1128 URL to Code....1128 Cross-References....1128 Recommended Reading....1128 Decision Trees....1128 Synonyms....1128 Definition....1128 Key Points....1128 Cross-References....1129 Recommended Reading....1129 Declarative Networking....1129 Synonyms....1129 Definition....1129 Historical Background....1129 Foundations....1130 Key Applications....1131 Future Directions....1131 URL to Code....1131 Cross-References....1131 Recommended Reading....1131 Deductive Data Mining Using Granular Computing....1132 Synonyms....1132 Definition of the Subject....1132 Scientific Fundamentals....1133 Isomorphism: A Critical Concept....1133 Granular Data Model: The Canonical Model....1134 Key Applications....1135 Constructing All Features....1135 High-Frequency Patterns in RDB....1135 Future Directions....1136 Non-semantic Phenomena in Data Mining....1136 Semantic Oriented Data Mining....1137 An Illustration....1138 Semantic clustering by homology....1138 Cross-References....1139 Recommended Reading....1139 Deduplication....1140 Synonyms....1140 Definition....1140 Key Points....1140 Cross-References....1141 Recommended Reading....1141 Deduplication in Data Cleaning....1141 Synonyms....1141 Definition....1141 Historical Background....1141 Foundations....1142 Multi-attribute Deduplication....1144 Constraints....1145 Key Applications....1145 Cross-References....1145 Recommended Reading....1145 Deep Instantiation....1146 Synonyms....1146 Definition....1146 Main Text....1146 Cross-References....1147 References....1147 Deep-Web Search....1147 Synonyms....1147 Definition....1147 Historical Background....1147 Foundations....1148 Search Architecture....1148 Source Modeling....1148 Schema Matching....1149 Offline Crawling....1150 Online Querying....1151 Key Applications....1151 Cross-References....1151 Recommended Reading....1151 Dense Index....1151 Definition....1151 Key Points....1152 Cross-References....1152 Recommended Reading....1152 Dense Pixel Displays....1152 Synonyms....1152 Definition....1153 Historical Background....1153 Foundations....1153 Dense Pixel Displays as Optimization Problem: Pixel Arrangement....1153 Dense Pixel Displays as Optimization Problem: Shape of Sub-windows....1155 Dense Pixel Displays as Optimization Problem: Ordering of Dimensions....1156 Key Applications....1156 Growth Matrix....1157 Pixel Bar Charts....1157 Literature Fingerprinting....1157 Cross-References....1158 Recommended Reading....1159 Density-Based Clustering....1159 Definition....1159 Historical Background....1159 Foundations....1160 DBSCAN....1161 GDBSCAN....1161 Denclue....1162 OPTICS....1162 Grid-Based Methods....1162 Key Applications....1163 Geographic Information Systems (GIS)....1163 Image Data....1163 Future Directions....1163 URL to Code....1163 Cross-References....1164 Recommended Reading....1164 Description Logics....1164 Synonyms....1164 Definition....1164 Historical Background....1164 Foundations....1165 Concept and Role Constructors....1165 Formal Semantics....1166 Using Concepts in Knowledge Bases....1166 Mathematical Properties....1167 Implementations....1167 Key Applications....1167 Conceptual Modeling....1167 Ontology Specification....1167 Management and Querying of Incomplete Information....1168 Query Organization and Optimization....1168 Future Directions....1168 URL to Code....1168 Cross-References....1168 Recommended Reading....1168 Design for Data Quality....1169 Synonyms....1169 Definition....1169 Historical Background....1169 Foundations....1170 Future Directions....1173 Cross-References....1173 Recommended Reading....1173 Dewey Decimal System....1174 Synonyms....1174 Definition....1174 Key Points....1174 Recommended Reading....1175 Diagram....1175 Synonyms....1175 Definition....1175 Key Points....1175 Cross-References....1177 Recommended Reading....1177 Difference....1177 Synonyms....1177 Definition....1177 Key Points....1177 Cross-References....1177 Digital Archives and Preservation....1177 Synonyms....1177 Definition....1178 Historical Background....1178 Foundations....1179 Key Applications....1180 Future Directions....1182 Cross-References....1183 Recommended Reading....1183 Digital Curation....1183 Synonyms....1183 Definition....1183 Key Points....1183 Cross-References....1184 Recommended Reading....1184 Digital Elevation Models....1184 Synonyms....1184 Definition....1184 Historical Background....1185 Foundations....1185 Key Applications....1188 Future Directions....1188 URL to Code....1188 Cross-References....1189 Recommended Reading....1189 Digital Libraries....1189 Synonyms....1189 Definition....1189 Historical Background....1189 Foundations....1190 Building Digital Libraries....1191 Key Applications....1191 Future Directions....1192 Experimental Results....1193 Data Sets....1193 Url to Code....1193 Cross-References....1193 Recommended Reading....1193 Digital Rights Management....1194 Synonyms....1194 Definition....1194 Historical Background....1194 Foundations....1194 Overview....1194 Watermarking for Rights Protection....1194 Consumer Driven Watermarking....1195 Numerical Data Types....1196 Categorical Data Types....1197 Key Applications....1198 Future Directions....1198 Cross-References....1199 Recommended Reading....1199 Digital Signatures....1199 Synonyms....1199 Definition....1199 Historical Background....1200 Foundations....1200 Digital Signature Schemes....1201 Digital Signature Schemes with Appendix....1202 Digital Signature Schemes with Message Recovery....1202 XML Signature....1203 Key Applications....1205 Cross-References....1205 Recommended Reading....1205 Dimension....1205 Definition....1205 Key Points....1205 Cross-References....1206 Recommended Reading....1206 Dimension Reduction Techniques for Clustering....1206 Synonyms....1206 Definition....1206 Historical Background....1207 Foundations....1207 Dimension Reduction Versus Feature Selection....1207 PCA and Other Linear Dimension Reduction....1207 Linear Discriminant Analysis....1208 Adaptive Dimension Reduction: Combining Dimension Reduction and Clustering....1209 Metric Scaling....1209 Laplacian Embedding and Other Nonlinear Dimension Reduction....1210 Laplacian Embedding....1210 Relation to Spectral Clustering....1211 Other Nonlinear Embedding Methods....1211 Key Applications....1212 Cross-References....1212 Recommended Reading....1212 Dimensionality Reduction....1212 Definition....1212 Key Points....1213 Cross-References....1213 Recommended Reading....1213 Dimensionality Reduction Techniques for Nearest-Neighbor Computations....1214 Synonyms....1214 Definition....1214 Historical Background....1214 Scientific Fundamentals....1214 Dimensionality Reduction via SVD, PCA, and KLT....1215 Combining Clustering Methods and SVD....1215 CSVD to Build an Index for k-NN Queries....1216 Nearest-Neighbors Queries with Multiple Clusters....1217 Exact Versus Approximate k-NN Queries....1218 High-Dimensional Indices....1218 Further Work....1220 Cross-References....1220 Recommended Reading....1220 Dimension-Extended Topological Relationships....1221 Definition....1221 Historical Background....1221 Foundations....1222 Key Applications....1223 Future Directions....1224 Cross-References....1224 Recommended Reading....1224 Direct Attached Storage....1225 Synonyms....1225 Definition....1225 Key Points....1225 Cross-References....1225 Recommended Reading....1225 Direct Manipulation....1225 Synonyms....1225 Definition....1226 Key Points....1226 Cross-References....1226 Recommended Reading....1226 Disaster Recovery....1227 Definition....1227 Key Points....1227 Cross-References....1227 Disclosure Risk....1227 Synonyms....1227 Definition....1227 Key Points....1227 Cross-References....1228 Recommended Reading....1228 Discounted Cumulated Gain....1228 Synonyms....1228 Definition....1228 Historical Background....1229 Foundations....1229 Ranked Retrieval Result....1229 Document Relevance Scores and Weights....1229 Gain Vector....1229 Cumulated Gain Vector....1229 Discounting Principle....1229 Discounted Cumulated Gain Vector....1230 Average Vector....1230 Ideal Vector....1230 Normalized Vector....1230 Normalized Discounted Cumulated Gain (nDCG) Vector....1230 The Average Normalized Discounted Cumulated Gain Indicator....1231 Properties of (n)(D)CG....1231 Key Applications....1232 Future Directions....1232 Session-Based DCG....1232 Cross-References....1233 Recommended Reading....1233 Discovery....1234 Synonyms....1234 Definition....1234 Historical Background....1234 Foundations....1235 Enabling Discovery....1235 Searching in Service Registries....1235 Querying Repositories....1236 Domain-Specific Knowledge in Service Descriptions....1236 Semantic Annotations....1236 Quality-of-Service Properties....1237 Key Applications....1237 Future Directions....1238 URL to Code....1238 Cross-References....1238 Recommended Reading....1238 Discrete Wavelet Transform and Wavelet Synopses....1238 Definition....1238 Historical Background....1239 Foundations....1239 Haar Wavelet Basics....1239 Data Reduction and Approximate Query Processing....1241 Conventional and Advanced Wavelet Thresholding Schemes....1242 Extended and Streaming Wavelet Synopses....1244 Key Applications....1244 Data Sets....1245 Future Directions....1245 Cross-References....1245 Recommended Reading....1245 Discretionary Access Control....1246 Synonyms....1246 Definition....1246 Historical Background....1246 Scientific Fundamentals....1246 DAC in Relational Database....1247 Research Issues in Emerging Systems....1248 Key Applications....1248 Future Directions....1248 Experimental Results....1249 Data Sets....1249 URL to Code....1249 Cross-Reference....1249 Recommended Reading....1249 Disk....1249 Synonyms....1249 Definition....1249 Key Points....1250 Cross-References....1250 Disk Power Saving....1250 Definition....1250 Key Points....1251 Cross-References....1251 Recommended Reading....1251 Distortion Techniques....1251 Synonyms....1251 Definition....1251 Historical Background....1252 Foundations....1252 Key Applications....1257 Cross-References....1257 Recommended Reading....1257 Distributed Architecture....1258 Synonyms....1258 Definition....1258 Historical Background....1259 Foundations....1260 Autonomy and Heterogeneity....1260 Transparency....1261 Distributed or Parallel DBMS Provide Update Transparency....1261 Consistency....1262 Distributed Catalog Management....1263 Cross-References....1263 Recommended Reading....1263 Distributed Concurrency Control....1263 Synonyms....1263 Definition....1263 Historical Background....1264 Foundations....1264 Future Directions....1267 Cross-References....1268 Recommended Reading....1268 Distributed Data Streams....1268 Definition....1268 Historical Background....1268 Foundations....1269 Key Applications....1274 Future Directions....1274 Data Sets....1275 Cross-References....1275 Recommended Reading....1275 Distributed Database Design....1276 Synonyms....1276 Definition....1276 Historical Background....1277 Foundations....1277 Fragmentation....1277 Allocation....1279 Future Directions....1279 Cross-References....1280 Recommended Reading....1280 Distributed Database Systems....1280 Synonyms....1280 Definition....1280 Historical Background....1281 Foundations....1281 Key Applications....1282 Future Directions....1282 Cross-References....1283 Recommended Reading....1283 Distributed DBMS....1283 Synonyms....1283 Definition....1283 Historical Background....1283 Foundations....1283 Data Placement Among Sites....1284 Propagating the Effects of Update Transactions....1284 Distributed Query Processing....1285 Handling Failures....1285 Key Applications....1286 Future Directions....1286 Cross-References....1286 Recommended Reading....1286 Distributed Deadlock Management....1287 Synonyms....1287 Definition....1287 Historical Background....1287 Foundations....1289 Transaction Wait-for Graph....1289 Deadlock Models....1290 Static vs Dynamic Deadlock Detection....1290 Deadlock Resolution....1290 Key Applications....1291 Future Directions....1291 Cross-References....1291 Recommended Reading....1291 Distributed File Systems....1292 Synonyms....1292 Definition....1292 Historical Background....1292 Scientific Fundamentals....1293 Architecture....1293 Naming Schemes....1294 Remote File Access....1294 Replication....1295 Caching....1295 Fault Tolerance and Scalability....1295 Security....1295 Key Applications....1295 Database Systems and Big Data Analytics....1295 Search Engines....1296 Cloud Computing....1296 Misc....1296 Future Directions....1296 Recommended Reading....1296 Distributed Hash Table....1296 Synonyms....1296 Definition....1297 Key Points....1297 Cross-References....1297 Recommended Reading....1297 Distributed Join....1297 Synonyms....1297 Definition....1297 Historical Background....1297 Foundations....1298 Site Selection....1298 Relation Transfer....1298 Local Join Processing....1299 Sequential Versus Pipelined Processing....1299 Algorithms....1300 Key Applications....1300 Experimental Results....1301 Cross-References....1301 Recommended Reading....1301 Distributed Machine Learning....1302 Synonyms....1302 Definition....1302 Historical Background....1302 Scientific Fundamentals....1302 Parallelizing Algorithms....1302 Gradient Descent....1303 Regression....1303 K-Means Clustering....1304 Ensemble Learning....1304 Frameworks....1304 Database Systems....1304 General Frameworks....1305 Purpose-Built Frameworks....1306 Key Applications....1306 Cross-References....1306 Recommended Reading....1306 Distributed Query Optimization....1307 Synonyms....1307 Definition....1307 Historical Background....1307 Foundations....1308 Fragmentation and Replication....1308 Plan Enumeration....1309 Total Cost Model and Response Time....1309 Static Versus Dynamic Distributed Query Optimization....1310 Global Versus Local, Centralized Versus Distributed Query Optimization, and Economical Models....1311 Future Directions....1311 Cross-References....1311 Recommended Reading....1311 Distributed Query Processing....1312 Synonyms....1312 Definition....1312 Historical Background....1312 Foundations....1313 Phases of Distributed Query Processing....1313 Data Localization....1314 Optimization of Distributed Queries....1315 Query Execution....1316 Key Applications....1317 Cross-References....1317 Recommended Reading....1317 Distributed Recovery....1318 Synonyms....1318 Definition....1318 Historical Background....1318 Foundations....1319 Key Applications....1320 Future Directions....1320 Cross-References....1321 Recommended Reading....1321 Distributed Spatial Databases....1321 Definition....1321 Historical Background....1321 Foundations....1322 Distributed Query Processing....1323 Distributed Spatial Indices....1325 Spatial Queries Involving Numerous Mobile Clients....1326 Key Applications....1327 Cross-References....1327 Recommended Reading....1327 Distributed Transaction Management....1328 Synonyms....1328 Definition....1328 Historical Background....1328 Foundations....1329 Distributed Transaction Management....1329 Serializability Theory....1329 Key Applications....1330 Future Directions....1331 Cross-References....1331 Recommended Reading....1331 Divergence-from-Randomness Models....1332 Synonyms....1332 Definition....1332 Historical Background....1332 Foundations....1332 Document Models....1333 Term Models....1334 Document Length Normalization....1334 Examples of Document Models....1334 Key Applications....1335 Future Directions....1335 URL to Code....1335 Cross-References....1335 Recommended Reading....1335 D-Measure....1335 Definition....1335 Main Text....1336 Cross-References....1336 Document....1336 Definition....1336 Key Points....1336 Cross-References....1337 Document Clustering....1337 Synonyms....1337 Definition....1337 Historical Background....1337 Foundations....1337 Document Representation....1338 Similarity Measures....1338 Partitional Document Clustering....1338 Criterion Function....1339 Optimization Method....1340 Agglomerative Document Clustering....1340 Evaluation of Document Clustering....1341 Key Applications....1342 URL to Code....1342 Data Sets....1342 Cross-References....1342 Recommended Reading....1342 Document Databases....1343 Synonyms....1343 Definition....1343 Historical Background....1343 Foundations....1343 Key Applications....1344 Cross-References....1344 Recommended Reading....1344 Document Field....1344 Definition....1344 Key Points....1345 Cross-References....1345 Recommended Reading....1345 Document Length Normalization....1345 Synonyms....1345 Definition....1345 Key Points....1345 Cross-References....1346 Recommended Reading....1346 Document Links and Hyperlinks....1347 Definition....1347 Key Points....1347 Cross-References....1347 Recommended Reading....1347 Document Representations (Inclusive Native and Relational)....1347 Synonyms....1347 Definition....1348 Historical Background....1348 Foundations....1349 Native Representations....1349 Page-Oriented Representations....1349 Stream-Oriented Representations....1349 Tree-Structured Representations....1350 Hybrid Representations....1351 Relational Representations....1351 Large Object Representation....1351 Shredded Representation....1351 Key Applications....1352 Cross-References....1352 Recommended Reading....1352 .NET Remoting....1353 Synonyms....1353 Definition....1353 Key Points....1353 Cross-References....1353 Recommended Reading....1354 Dublin Core....1354 Definition....1354 Historical Background....1354 Foundations....1354 Qualified Dublin Core....1355 Encoding Dublin Core....1356 Key Applications....1356 Cross-References....1356 Recommended Reading....1356 Dynamic Graphics....1357 Synonyms....1357 Definition....1357 Historical Background....1357 Foundations....1358 Key Applications....1360 Future Directions....1360 URL to Code....1360 Cross-References....1360 Recommended Reading....1361 Dynamic Web Pages....1361 Definition....1361 Key Points....1361 Cross-References....1362 E....1363 eAccessibility....1363 Definition....1363 Historical Background....1363 Foundations....1364 Key Applications....1365 Web Accessibility....1365 Media Accessibility....1365 Accessibility in Education....1366 Game Accessibility....1366 Mobile Accessibility....1366 Future Directions....1367 Cross-References....1367 Recommended Reading....1367 ECA Rule Action....1368 Definition....1368 Key Points....1369 Cross-References....1369 ECA Rule Condition....1369 Definition....1369 Key Points....1369 Cross-References....1369 ECA Rules....1369 Synonyms....1369 Definition....1369 Historical Background....1369 Foundations....1370 Cross-References....1370 Recommended Reading....1370 E-Commerce Transactions....1370 Synonyms....1370 Definition....1370 Key Points....1370 Cross-References....1371 Recommended Reading....1371 Effectiveness Involving Multiple Queries....1371 Synonyms....1371 Definition....1371 Historical Background....1372 Foundations....1372 Key Applications....1373 Data Sets....1373 URL to Code....1373 Cross-References....1373 Recommended Reading....1373 Ehrenfeucht-Fraïssé Games....1374 Synonyms....1374 Definition....1374 Key Points....1374 Cross-References....1375 Recommended Reading....1375 Elasticity....1375 Synonyms....1375 Definition....1375 Cross-References....1375 References....1376 Electronic Dictionary....1376 Synonyms....1376 Definition....1376 Historical Background....1376 Foundations....1377 Key Applications....1378 Cross-References....1378 Recommended Reading....1378 Electronic Encyclopedia....1378 Synonyms....1378 Definition....1378 Key Points....1378 Cross-References....1379 Recommended Reading....1379 Electronic Health Record....1379 Synonyms....1379 Definition....1380 Historical Background....1380 Foundations....1380 Content....1381 Source....1382 Time....1382 Key Applications....1383 Cross-References....1384 Recommended Reading....1384 Electronic Ink Indexing....1385 Synonyms....1385 Definition....1385 Historical Background....1385 Foundations....1386 Electronic Ink Representation....1386 Hidden Markov Models (HMMs)....1387 Representation Granularity....1388 Indexing Techniques....1388 Alphabet-Level Indexing....1389 Stroke-Level Indexing....1390 Pictogram-Level Indexing....1390 Handwritten Ink as a Special Form of Time-Sequence Data....1390 Cross-References....1390 Recommended Reading....1391 Electronic Newspapers....1391 Definition....1391 Historical Background....1391 Foundations....1392 Managing Content....1392 Metadata....1392 Digital Asset Management Systems....1392 Automated Text Processing of News Resources....1392 Information Extraction and Text Data Mining....1393 Event Detection and Tracking....1393 Commercial News Aggregators, News Summarization, and Searching....1393 Additional Services and Issues....1393 Preservation Services....1393 Rights Management....1393 Managing Multimedia News Content....1394 Presentation and Access Services....1394 Personalized Interaction....1394 Recommendations....1394 Cross-References....1394 Recommended Reading....1394 Eleven Point Precision-Recall Curve....1395 Definition....1395 Key Points....1395 Cross-References....1396 Emergent Semantics....1396 Synonyms....1396 Definition....1396 Historical Background....1396 Foundations....1397 Key Applications....1398 Cross-References....1399 Recommended Reading....1399 Emerging Pattern Based Classification....1399 Synonyms....1399 Definition....1399 Key Points....1399 Cross-References....1400 Recommended Reading....1400 Emerging Patterns....1400 Synonyms....1400 Definition....1400 Historical Background....1401 Foundations....1401 Key Applications....1402 Cross-References....1402 Recommended Reading....1402 Ensemble....1403 Synonyms....1403 Definition....1403 Historical Background....1403 Foundations....1403 Terminologies....1403 Methods....1404 Why Useful?....1405 Accuracy and Diversity....1405 Key Applications....1406 Future Directions....1406 Experimental Results....1406 Data Sets....1406 Url To Code....1406 Cross-References....1406 Recommended Reading....1406 Enterprise Application Integration....1407 Synonyms....1407 Definition....1407 Historical Background....1407 Foundations....1408 Approaches to Application Integration....1410 Connecting to Applications....1410 Standards for Application Integration....1412 Key Applications....1412 Cross-References....1413 Recommended Reading....1413 Enterprise Content Management....1413 Synonyms....1413 Definition....1413 Key Points....1414 Cross-References....1414 Recommended Reading....1414 Enterprise Service Bus....1414 Synonyms....1414 Definition....1414 Historical Background....1414 Foundations....1415 The ESB and Connectivity....1415 ESB Core Principles....1416 The ESB in an SOA Context....1416 Key Applications....1417 Cross-References....1417 Recommended Reading....1417 Enterprise Terminology Services....1417 Definition....1417 Historical Background....1417 Foundations....1418 System Architecture....1418 Key Applications....1418 Case Studies and Experiences....1418 Cross-References....1421 Recommended Reading....1421 Entity Relationship Model....1421 Synonyms....1421 Definition....1421 Historical Background....1421 Foundations....1422 Entities, Entity Types, and Attributes....1422 Relationships and Relationship Types....1422 Cardinality and Participation Constraints....1423 Attributes of a Relationship....1425 Roles....1425 Ternary Relationships....1425 Weak Entity Types....1425 ER Modeling Techniques....1426 Translation of ERDs into a Relational Schema....1426 Key Applications....1427 URL to Code....1427 Cross-References....1427 Recommended Reading....1427 Entity Resolution....1428 Synonyms....1428 Definition....1428 Historical Background....1428 Scientific Fundamentals....1429 Pairwise Matching....1429 Clustering....1429 Blocking....1430 Key Applications....1430 Data Cleaning....1430 Data Integration and Data Warehousing....1430 Experimental Results....1431 Data Sets....1431 Url to Code....1431 Cross-References....1431 Recommended Reading....1431 Entity Retrieval....1432 Synonyms....1432 Definition....1432 Historical Background....1432 Scientific Fundamentals....1433 Characteristics of Entities....1433 Ranking Term-Based Entity Representations....1433 Incorporating Type Information....1434 Exploiting and Searching Relationships....1435 Key Applications....1435 Future Directions....1435 Data Sets....1435 Cross-References....1436 Recommended Reading....1436 Equality-Generating Dependencies....1437 Synonyms....1437 Definition....1437 Key Points....1437 Cross-References....1437 Recommended Reading....1437 ERR-IA....1438 Synonyms....1438 Definition....1438 Main Text....1438 Cross-References....1438 Escrow Transactions....1438 Synonyms....1438 Definition....1438 Key Points....1439 Escrow Commits and Aborts....1440 Distributed Escrow Transactions....1440 Cross-References....1441 Recommended Reading....1441 European Law in Databases....1441 Synonyms....1441 Definition....1441 Historical Background....1441 Foundations....1441 Eligibility....1442 Scope of Rights: Extraction or Reutilization....1442 Exceptions and Limitations....1442 Key Applications....1443 Cross-References....1443 Recommended Reading....1443 Evaluation Metrics for Structured Text Retrieval....1444 Synonyms....1444 Definition....1444 Historical Background....1444 Foundations....1445 Evaluation Concepts....1445 XML Retrieval Tasks....1445 User Behavior....1446 Relevance Dimensions....1446 Quantization....1446 Ideality....1446 Construction of Ideal Sets and Lists....1447 Near Misses and Overlap....1447 Metric Properties....1447 Evaluation Metrics....1448 The inex_eval Metric....1448 The inex_eval_ng Metric....1449 The XCG Metrics....1450 Gain and Overlap....1450 XCG Metrics....1450 The T2I Metric....1451 The (E)PRUM and GR Metrics....1451 The User Model....1451 GR, PRUM and EPRUM....1452 The HiXEval Metric....1452 Key Applications....1453 Web Search....1453 Digital Libraries....1454 URL to Code....1454 Cross-References....1454 Recommended Reading....1454 Evaluation of Relational Operators....1454 Synonyms....1454 Definition....1455 Historical Background....1455 Foundations....1455 Pipelined Query Execution....1455 Selection....1455 Selection Based on Scanning....1456 Selection Based on Indexing....1456 Projection....1456 Joins....1456 Nested Loops Join....1456 Block Nested Loops Join....1457 Index Nested Loops Join....1457 Sort-Merge Join....1457 Hash Join....1458 Grace Hash Join....1458 Hybrid Hash Join....1458 Aggregation....1459 Aggregation Based on Sorting....1459 Aggregation Based on Hashing....1459 Key Applications....1460 Cross-References....1460 Recommended Reading....1460 Event and Pattern Detection over Streams....1460 Synonyms....1460 Definition....1460 Historical Background....1460 Foundations....1461 Event Pattern Query Model....1461 Event Pattern Query Processing....1462 Key Applications....1463 Future Directions....1463 Cross-References....1463 Recommended Reading....1464 Event Causality....1464 Definition....1464 Key Points....1465 Cross-References....1465 Recommended Reading....1465 Event Channel....1465 Synonyms....1465 Definition....1466 Key Points....1466 Cross-References....1466 Recommended Reading....1466 Event Cloud....1466 Definition....1466 Key Points....1466 Cross-References....1467 Recommended Reading....1467 Event Detection....1467 Synonyms....1467 Definition....1467 Historical Background....1467 Foundations....1469 Key Applications....1471 Future Directions....1471 Cross-References....1472 Recommended Reading....1472 Event Driven Architecture....1473 Synonyms....1473 Definitions....1473 Historical Background....1473 Foundations....1473 Measures for Evaluating Event Driven Applications....1473 Components of Event Driven Architectures....1474 Responders....1475 Communication Layer....1475 Administration Layer....1475 System Specification....1475 Key Applications....1476 Future Directions....1476 Cross-References....1476 Recommended Reading....1476 Event Flow....1477 Synonyms....1477 Definition....1477 Key Points....1477 Cross-References....1477 Recommended Reading....1477 Event in Active Databases....1477 Definition....1477 Key Points....1478 Cross-References....1478 Recommended Reading....1478 Event in Temporal Databases....1478 Synonyms....1478 Definition....1478 Key Points....1478 Cross-References....1479 Recommended Reading....1479 Event Lineage....1479 Synonyms....1479 Definition....1479 Key Points....1479 Cross-References....1479 Recommended Reading....1479 Event Pattern Detection....1479 Synonyms....1479 Definition....1480 Historical Background....1480 Foundations....1480 Key Applications....1481 Cross-References....1481 Recommended Reading....1482 Event Prediction....1482 Synonyms....1482 Definition....1482 Historical Background....1482 Foundations....1482 Mechanisms for Event Prediction....1483 Influencing the Occurrence of Future Events....1485 Key Applications....1486 Future Directions....1486 Cross-References....1486 Recommended Reading....1486 Event Processing Agent....1486 Synonyms....1486 Definition....1486 Key Points....1487 Cross-References....1487 Recommended Reading....1487 Event Processing Network....1487 Synonyms....1487 Definition....1487 Historical Background....1488 Foundations....1488 Event Channel....1488 Event Producer and Consumer....1489 Event Processing Agent....1489 Pattern Detection....1490 Processing....1492 Emission....1492 Key Applications....1493 Information Dissemination\Situation Awareness....1493 Active Diagnostics....1493 Real Time Enterprise....1493 Business Activity Monitoring....1493 Predictive Processing....1493 Cross-References....1493 Recommended Reading....1493 Event Sink....1493 Synonyms....1493 Definition....1493 Key Points....1493 Cross-References....1494 Recommended Reading....1494 Event Source....1494 Synonyms....1494 Definition....1494 Key Points....1494 Cross-References....1494 Recommended Reading....1494 Event Specification....1495 Synonyms....1495 Definition....1495 Historical Background....1495 Foundations....1496 Key Applications....1497 Future Directions....1498 Cross-References....1498 Recommended Reading....1498 Event Stream....1499 Synonyms....1499 Definition....1499 Key Points....1499 Cross-References....1499 Recommended Reading....1499 Event Transformation....1500 Synonyms....1500 Definition....1500 Historical Background....1500 Foundations....1500 Translation....1502 Splitting....1503 Aggregation....1504 Composition....1504 Key Applications....1504 Cross-References....1505 Recommended Reading....1505 Event-Driven Business Process Management....1505 Synonyms....1505 Definition....1505 Historical Background....1505 Foundations....1505 The Business Process Modeler....1506 The Event Modeler....1507 Event Processing Languages....1507 Relation to the Database Technology....1507 Examples....1508 Key Applications....1508 Cross-References....1508 Recommended Reading....1508 Eventual Consistency....1509 Synonyms....1509 Definition....1509 Formal Definition and Usage....1509 Cross-References....1510 Recommended Reading....1510 Evidence-Based Medicine....1510 Synonyms....1510 Definition....1510 Key Points....1510 Cross-References....1511 Recommended Reading....1511 Executable Knowledge....1511 Synonyms....1511 Definition....1511 Historical Background....1512 Scientific Fundamental....1512 Key Applications....1516 Future Directions....1517 Cross-References....1518 Recommended Reading....1518 Execution Skew....1518 Definition....1518 Key Points....1518 Cross-References....1519 Recommended Reading....1519 Expected Reciprocal Rank....1519 Synonyms....1519 Definition....1519 Main Text....1519 Cross-References....1519 Explicit Event....1520 Definition....1520 Key Points....1520 Cross-References....1520 Exploratory Data Analysis....1520 Definition....1520 Key Points....1520 Cross-References....1521 Recommended Reading....1521 Expressive Power of Query Languages....1521 Definition....1521 Historical Background....1521 Foundations....1521 Key Applications....1523 Cross-References....1523 Recommended Reading....1524 Extended Entity-Relationship Model....1524 Synonyms....1524 Definition....1524 Historical Background....1524 Scientific Fundamentals....1525 An Example of an EER Diagram....1525 The Definition Scheme for Structures....1525 Structures in Detail....1526 Attribute Types and Attribute Values....1526 Entity Types and Entity Classes....1527 Cluster Types and Cluster Classes....1527 Relationship Types and Relationship Classes....1527 Integrity Constraints....1529 Schemata....1530 Graphical Representation....1531 Key Applications....1531 Future Directions....1532 URL to Code....1533 Cross-References....1533 Recommended Reading....1533 Extended Transaction Models and the ACTA Framework....1534 Synonyms....1534 Definition....1534 Key Points....1534 Cross-References....1535 Recommended Reading....1535 Extendible Hashing....1535 Definition....1535 Historical Background....1536 Foundations....1536 Structure....1536 Overflow Handling....1536 Discussion....1537 Key Applications....1538 Cross-References....1538 Recommended Reading....1538 Extraction, Transformation, and Loading....1538 Synonyms....1538 Definition....1538 Historical Background....1538 Scientific Fundamentals....1539 Part I: General Description of an ETL Process....1539 Part II: Individual Steps....1541 Part III: Global Picture Revisited....1542 Key Applications....1544 Future Directions....1544 Data Sets....1545 Cross-References....1545 Recommended Reading....1545 F....1547 Faceted Search....1547 Synonyms....1547 Definition....1547 Historical Background....1547 Foundations....1548 An Example....1548 Faceted Organization....1549 Faceted Access....1550 Browsing....1550 Searching (and Integrated Browsing and Searching)....1552 Scale and Details....1552 Key Applications....1552 Future Directions....1553 Cross-References....1553 Recommended Reading....1553 Fault Tolerance and High Availability in Data Stream Management Systems....1554 Definition....1554 Historical Background....1554 Foundations....1555 Techniques for Handling Crash Failures....1555 Active Replicas....1556 Passive Replicas....1556 Failure Recovery....1557 Trade-Offs Among Crash Failure Techniques....1558 Techniques for Handling Network Partitions....1559 Optimizations....1559 Flux: Integrating Fault Tolerance and Load Balancing....1559 Leveraging Replication for Availability and Performance in Wide Area Networks....1559 Passive Standby: Distributed Checkpointing and Parallel Recovery....1560 Key Applications....1560 Future Directions....1560 Experimental Results....1560 URL to Code....1560 Cross-References....1560 Recommended Reading....1560 Feature Extraction for Content-Based Image Retrieval....1561 Synonyms....1561 Definition....1561 Historical Background....1561 Foundations....1562 Key Applications....1565 Cross-References....1565 Recommended Reading....1565 Feature Selection for Clustering....1565 Definition....1565 Historical Background....1566 Foundations....1568 An Example of a Filter-Global Method....1568 Distance-Based Entropy Measure....1569 Other Methods....1570 Trace Measure....1570 EM Method....1570 Conceptual Clustering....1570 Important Applications....1571 URL....1571 Cross-References....1572 Recommended Reading....1572 Feature-Based 3D Object Retrieval....1573 Synonyms....1573 Definition....1573 Historical Background....1573 Foundations....1574 Common Requirements of 3D Feature Extraction....1574 3D Feature Extraction Process Model....1574 3D Feature Types....1575 Query Modalities....1575 Efficient 3D Object Retrieval....1575 Key Applications....1576 Industrial Applications....1576 Medicine....1576 Molecular Biology....1576 Cultural Heritage....1576 Future Directions....1576 Experimental Results....1576 Cross-References....1576 Recommended Reading....1577 Field-Based Information Retrieval Models....1577 Definition....1577 Historical Background....1577 Foundations....1578 Key Applications....1580 Future Directions....1580 Data Sets....1581 Cross-References....1581 Recommended Reading....1581 Field-Based Spatial Modeling....1582 Definition....1582 Historical Background....1582 Foundations....1584 Key Applications....1586 Future Directions....1587 Cross-References....1588 Recommended Reading....1588 First-Order Logic: Semantics....1588 Synonyms....1588 Definition....1588 Key Points....1589 Cross-References....1590 Recommended Reading....1590 First-Order Logic: Syntax....1590 Synonyms....1590 Definition....1590 Key Points....1590 Recommended Reading....1592 Fixed Time Span....1592 Synonyms....1592 Definition....1592 Key Points....1592 Cross-References....1592 Recommended Reading....1592 Flex Transactions....1592 Synonyms....1592 Definition....1592 Key Points....1593 Cross-References....1593 Recommended Reading....1593 FM Synopsis....1593 Synonyms....1593 Definition....1594 Historical Background....1594 Foundations....1594 Optimizations....1595 Extensions....1597 Key Applications....1597 Experimental Results....1598 Cross-References....1598 Recommended Reading....1598 F-Measure....1598 Synonyms....1598 Definition....1598 Key Points....1599 Cross-References....1599 Focused Web Crawling....1599 Synonyms....1599 Definition....1599 Historical Background....1599 Foundations....1600 Setting Crawl Priorities Using Web Graph Properties....1600 Basic Topic-Focused Crawler....1601 Focused Crawling Using Context Graphs....1602 Training a Focused Crawler Online....1602 Reinforcement Learning Using Markov Models....1604 Key Applications....1606 Future Directions....1606 Cross-References....1606 Recommended Reading....1607 FOL Modeling of Integrity Constraints (Dependencies)....1607 Synonyms....1607 Definition....1607 Historical Background....1608 Foundations....1608 Functional Dependencies....1608 Key Dependencies....1609 Join Dependencies....1609 Multi-Valued Dependencies....1609 Inclusion Dependencies....1609 Foreign Key Dependencies....1610 Expressing Dependencies in First-Order Logic....1610 Embedded Dependencies....1610 Functional Dependencies....1610 Join Dependencies....1610 Inclusion Dependencies....1611 Other Classes of Dependencies....1611 Other Constraints....1611 Cardinality Constraints....1611 Domain Constraints....1611 Representational Constraints....1612 Key Applications....1612 Schema Design....1612 Automatic Integrity Enforcement....1613 Query Optimization....1613 A Unified View of Dependencies....1613 Cross-References....1613 Recommended Reading....1613 Forever....1614 Synonyms....1614 Definition....1614 Key Points....1614 Cross-References....1615 Recommended Reading....1615 Form....1615 Synonyms....1615 Definition....1615 Historical Background....1615 Foundations....1617 Form Composition....1617 Generating Forms....1618 Key Applications....1619 Business Database Applications....1619 End-User Programming and Domain Specific Application Development....1619 Ubiquitous Computing....1619 Data Quality....1619 Meta-data Capture....1619 Knowledge Bases....1620 Cross-References....1620 Recommended Reading....1620 Fourth Normal Form....1620 Synonyms....1620 Definition....1620 Key Points....1621 Cross-References....1621 Recommended Reading....1621 FQL....1621 Definition....1621 Key Points....1622 Cross-References....1622 Recommended Reading....1622 Fractal....1622 Synonyms....1622 Definition....1622 Key Points....1622 Cross-References....1623 Recommended Reading....1623 Frequency Moments....1624 Synonyms....1624 Definition....1624 Key Points....1624 Cross-References....1625 Recommended Reading....1625 Frequent Graph Patterns....1625 Synonyms....1625 Definition....1625 Historical Background....1626 Foundations....1626 Canonical Adjacency Matrix....1626 CAM Tree....1628 Frequent Subgraph Mining of a Graph Database....1628 FFSM....1629 FFSM-Explore....1629 Key Applications....1629 Pattern Discovery from Chemical Structures....1630 Pattern Discovery from Protein Structures....1630 Cross-References....1630 Recommended Reading....1630 Frequent Items on Streams....1630 Synonyms....1630 Definition....1631 Historical Background....1631 Foundations....1631 Problem Approximations....1631 Proposed Algorithms....1631 Counter-Based Techniques....1631 Sketch-Based Techniques....1633 Generalizations....1633 Generalization for Weighted Updates....1634 Generalization for Time Decay and Sliding Window....1634 Generalization for Distributed Streams....1634 Key Applications....1635 Experimental Results....1635 Cross-References....1636 Recommended Reading....1636 Frequent Itemset Mining with Constraints....1637 Synonyms....1637 Definition....1637 Historical Background....1637 Foundations....1638 Key Applications....1641 Data Sets....1641 Cross-References....1641 Recommended Reading....1642 Frequent Itemsets and Association Rules....1642 Synonyms....1642 Definition....1642 Historical Background....1642 Scientific Fundamentals....1643 Key Applications....1644 Association and Correlation Analysis....1644 Frequent Pattern-Based Classification and Clustering....1645 Biological Data Analysis....1645 Web Mining and Software Bug Mining....1645 Future Directions....1645 Experimental Results....1646 Data Sets....1646 URL to Code....1646 Cross-References....1646 Recommended Reading....1646 Frequent Partial Orders....1647 Definition....1647 Historical Background....1647 Foundations....1647 Finding Frequent Closed Partial Orders Using Frequent Itemset Mining Algorithms....1648 Finding Transitive Reductions of Frequent Closed Partial Orders Directly....1649 Key Applications....1649 Cross-References....1650 Recommended Reading....1650 Fully Automatic Web Data Extraction....1650 Synonyms....1650 Definition....1650 Historical Background....1650 Foundations....1651 Key Applications....1652 Data Sets....1653 Cross-References....1653 Recommended Reading....1653 Functional Data Model....1654 Definition....1654 Historical Background....1654 Foundations....1655 Semantic Web Vision and RDFS....1656 Mapping a Functional Model to RDFS....1656 Constraints....1656 Updating Functional Data....1657 Key Applications....1658 Future Directions....1658 URL to Code....1658 Cross-References....1658 Recommended Reading....1658 Functional Dependencies for Semistructured Data....1659 Synonyms....1659 Definition....1659 Key Points....1659 Cross-References....1661 Recommended Reading....1661 Functional Dependency....1661 Synonyms....1661 Definition....1661 Key Points....1661 Cross-References....1662 Recommended Reading....1662 Functional Query Language....1662 Definition....1662 Historical Background....1662 Foundations....1663 Comprehensions in P/FDM and Constraints....1664 Comprehensions in Kleisli – Records, Lists and Mixed Types....1664 Comprehensions in FDL and PFL....1665 Key Applications....1665 Future Directions....1665 URL to Code....1666 Cross-References....1666 Recommended Reading....1666 Fuzzy Models....1666 Synonyms....1666 Definition....1666 Historical Background....1667 Scientific Fundamentals....1667 Generalizations of the Boolean Query Language....1667 A Flexible Extension of XQuery Full-Text....1669 Flexible Indexing of Semi-structured Documents....1669 Fuzzy Associative Mechanisms....1670 Prioritized Aggregation of Multiple Relevance Assessments....1670 Fuzzy Approaches to Distributed Information Retrieval....1671 Key Applications....1671 Cross-References....1671 Recommended Reading....1671 Fuzzy Relation....1672 Definition....1672 Key Points....1672 Cross-References....1672 Recommended Reading....1672 Fuzzy Set....1672 Definition....1672 Key Points....1673 Cross-References....1673 Recommended Reading....1673 Fuzzy Set Approach....1674 Synonyms....1674 Definition....1674 Historical Background....1674 Scientific Fundamentals....1675 Key Applications....1677 Cross-Reference....1678 Recommended Reading....1678 Fuzzy/Linguistic IF-THEN Rules and Linguistic Descriptions....1678 Definition....1678 Key Points....1679 Cross-References....1679 Recommended Reading....1679 G....1680 Gazetteers....1680 Synonyms....1680 Definition....1680 Key Points....1680 Cross-References....1681 Recommended Reading....1681 Gene Expression Arrays....1681 Definition....1681 Historical Background....1681 Foundations....1681 Key Applications....1682 Future Directions....1684 Data Sets....1684 Cross-References....1684 Recommended Reading....1684 Generalization of ACID Properties....1684 Synonyms....1684 Definition....1685 Key Points....1685 Cross-References....1686 Recommended Reading....1686 Generalized Search Tree....1686 Synonyms....1686 Definition....1686 Historical Background....1686 Foundations....1687 Key Applications....1687 URL to Code....1688 Cross-References....1688 Recommended Reading....1688 Genetic Algorithms....1688 Synonyms....1688 Definition....1688 Historical Background....1689 Foundations....1689 Key Applications....1691 Experimental Results....1691 Cross-References....1692 Recommended Reading....1692 Geo Raster Data Management....1692 Definition....1692 Historical Background....1692 Scientific Fundamentals....1695 Key Applications....1697 Satellite Imagery....1697 Atmospheric Modeling....1697 Future Directions....1697 Experimental Results....1699 Data Sets....1699 Url to Code....1699 Cross-References....1699 Recommended Reading....1700 Geographic Information System....1700 Synonyms....1700 Definition....1700 Historical Background....1701 Foundations....1701 Key Applications....1704 Future Directions....1704 Cross-References....1705 Recommended Reading....1705 Geographical Information Retrieval....1705 Definition....1705 Historical Background....1705 Foundations....1706 Detecting Geographic References....1706 Disambiguating Place Names....1707 Vague Geographic Terminology....1707 Spatial and Textual Indexing....1707 Geographical Relevance Ranking....1708 User Interfaces....1708 User Studies and Evaluation....1709 Key Applications....1709 Cross-References....1709 Recommended Reading....1709 Geography Markup Language....1710 Synonyms....1710 Definition....1710 Historical Background....1710 Scientific Fundamentals....1711 Base and Application Schema....1711 Profiles....1711 Key Applications....1712 Schemas for GML....1712 Examples....1713 Cross-References....1713 Recommended Reading....1713 Geometric Stream Mining....1713 Definition....1713 Historical Background....1714 Foundations....1714 Stream Models....1714 Classes of Problems....1714 Range Counting and Robust Statistics....1714 Extent Measures....1714 Geometric Graphs....1714 Nearest Neighbor and Skyline....1715 General Techniques....1715 Merge and Reduce....1715 Reduction to Vector Problems....1717 Random Sampling....1718 Key Applications....1719 Cross-References....1719 Recommended Reading....1719 GEO-RBAC Model....1719 Synonyms....1719 Definition....1720 Key Points....1720 Cross-References....1721 Recommended Reading....1721 Georeferencing....1721 Synonyms....1721 Definition....1721 Historical Background....1722 Foundations....1722 Technical Background....1722 Georeferencing Techniques....1723 Datasets....1724 Documents....1724 Maps....1724 Photographs....1724 Imagery....1724 Key Applications....1724 Cross-References....1725 Recommended Reading....1725 Geo-Social Networks....1725 Synonyms....1725 Definition....1725 Historical Background....1725 Foundations....1726 Data Management....1726 GeoSN Queries....1726 Recommendations and Predictions....1726 Metrics....1726 Properties....1727 Privacy....1727 Key Applications....1727 Future Directions....1727 Datasets....1727 URL to Code....1727 Recommended Reading....1727 Geospatial Metadata....1728 Synonyms....1728 Definition....1728 Historical Background....1728 Foundations....1729 GML: The Geography Markup Language....1730 Geospatial Metadata Catalog....1730 Cross-References....1730 Recommended Reading....1730 Geo-Targeted Web Search....1730 Synonyms....1730 Definition....1730 Historical Background....1730 Foundations....1731 Geo Parsing and Geo Coding....1731 Indexing and Query Execution....1732 Geographic Search Queries....1734 Key Applications....1734 Future Directions....1734 Cross-References....1735 Recommended Reading....1735 GMAP....1735 Synonyms....1735 Definition....1736 Key Points....1736 Cross-References....1736 Recommended Reading....1736 Grammar Inference....1736 Synonyms....1736 Definition....1736 Historical Background....1737 Foundations....1738 Key Applications....1739 Cross-References....1740 Recommended Reading....1740 Graph....1740 Synonyms....1740 Definition....1740 Key Points....1741 Cross-References....1741 Recommended Reading....1741 Graph Data Management in Scientific Applications....1741 Synonyms....1741 Definition....1741 Historical Background....1742 Foundations....1742 Graphs in Science....1742 Data Management for Large Graphs....1742 Data Management for Large Collections of Graphs....1743 Some Data Management Techniques....1743 Key Applications....1744 Cross-References....1744 Recommended Reading....1744 Graph Database....1744 Synonyms....1744 Definition....1745 Historical Background....1745 Foundations....1745 Key Applications....1747 Cross-References....1747 Recommended Reading....1747 Graph Management in the Life Sciences....1748 Definition....1748 Historical Background....1749 Foundations....1749 Types and Models of Graphs....1749 Properties of Biological Networks....1749 Graph Databases....1750 Graph Query Languages....1750 Graph Mining....1751 Key Applications....1751 Graph-Based Function Prediction....1751 Managing Biological Ontologies....1751 Management of Phylogenetic Trees....1752 Visualization of Biological Networks....1752 Future Directions....1752 URL to Code....1752 Cross-References....1753 Recommended Reading....1753 Graph Mining....1753 Synonyms....1753 Definition....1754 Historical Background....1754 Scientific Fundamentals....1754 Key Applications....1755 Graph Query Processing....1755 Graph Classification....1755 Future Directions....1755 Cross-References....1755 Recommended Reading....1755 Graph Mining on Streams....1756 Synonyms....1756 Definition....1756 Historical Background....1757 Foundations....1757 Key Applications....1760 Future Directions....1760 Cross-References....1760 Recommended Reading....1760 Graph OLAP....1761 Synonyms....1761 Definition....1761 Historical Background....1761 Scientific Fundamentals....1762 Key Applications....1765 Attributed Graphs Data Management Systems....1765 Decision Making Systems Over Graphs....1765 Future Directions....1765 Cross-References....1765 Recommended Reading....1765 Graphical Models for Uncertain Data Management....1766 Synonyms....1766 Definition....1766 Historical Background....1766 Scientific Fundamentals....1767 Key Applications....1772 Future Directions....1772 Recommended Reading....1772 Grid and Workflows....1773 Synonyms....1773 Definition....1773 Historical Background....1773 Foundations....1774 Key Applications....1774 Future Directions....1774 Experimental Results....1774 Cross-References....1776 Recommended Reading....1776 Grid File (and Family)....1776 Definition....1776 Historical Background....1777 Foundations....1777 Key Applications....1779 Spatial Databases....1779 Data Mining....1779 Data Warehouses....1780 Future Directions....1780 Experimental Results....1780 Cross-References....1780 Recommended Reading....1780 GUIs for Web Data Extraction....1780 Synonyms....1780 Definition....1780 Historical Background....1781 Foundations....1782 Key Applications....1784 Cross-References....1784 Recommended Reading....1784 H....1785 Hash Functions....1785 Synonyms....1785 Definition....1785 Key Points....1785 Cross-References....1786 Recommended Reading....1786 Hash Join....1786 Synonyms....1786 Definition....1786 Key Points....1786 Cross-References....1787 Recommended Reading....1787 Hash-Based Indexing....1787 Synonyms....1787 Definition....1787 Key Points....1787 Cross-References....1788 Recommended Reading....1788 Hierarchical Clustering....1788 Definition....1788 Historical Background....1789 Foundations....1789 Key Applications....1792 Cross-References....1792 Recommended Reading....1792 Hierarchical Data Model....1793 Synonyms....1793 Definition....1793 Historical Background....1793 Foundations....1793 Graphs and Hierarchies....1794 Preliminary Definitions....1794 Properties of Hierarchies....1794 IMS Data Structures....1795 The IMS Global Schema....1795 The IMS Logical Database....1796 Additional Constructs....1797 Entity-Relationship to Hierarchical Mapping....1797 Key Applications....1798 Cross-References....1798 Recommended Reading....1798 Hierarchical Data Summarization....1799 Synonyms....1799 Definition....1799 Historical Background....1799 Scientific Fundamentals....1800 Key Applications....1804 Future Directions....1804 URL to Code....1804 Cross-References....1804 Recommended Reading....1805 Hierarchical Heavy Hitter Mining on Streams....1805 Synonyms....1805 Definition....1806 Historical Background....1806 Foundations....1806 Key Applications....1808 Experimental Results....1808 Cross-References....1808 Recommended Reading....1809 Hierarchy....1809 Definition....1809 Key Points....1809 Cross-References....1810 Recommended Reading....1810 High-Dimensional Indexing....1810 Synonyms....1810 Definition....1811 Historical Background....1811 Foundations....1811 TV-Tree....1812 SS-Tree....1812 X-Tree....1812 Cost Model-Based Optimization Techniques....1813 Pyramid Technique....1814 VA-File....1814 IQ-Tree....1814 iDistance....1815 Modern Hardware....1816 Key Applications....1816 Cross-References....1817 Recommended Reading....1817 Histogram....1818 Definition....1818 Key Points....1818 Cross-References....1819 Recommended Reading....1819 Histograms on Streams....1819 Synonyms....1819 Definition....1819 Historical Background....1819 Foundations....1820 Key Applications....1822 Cross-References....1823 Recommended Reading....1823 History in Temporal Databases....1823 Synonyms....1823 Definition....1823 Key Points....1823 Cross-References....1824 Recommended Reading....1824 Homomorphic Encryption....1824 Definition....1824 Key Points....1824 RSA....1824 El Gamal....1824 Goldwasser-Micali....1825 Paillier....1825 Fully Homomorphic Encryption....1825 Cross-References....1825 Recommended Reading....1825 Horizontally Partitioned Data....1825 Synonyms....1825 Definition....1825 Historical Background....1825 Foundations....1826 Key Applications....1826 Future Directions....1827 Cross-References....1827 Recommended Reading....1827 Human Factors Modeling in Crowdsourcing....1827 Synonyms....1827 Definition....1828 Historical Background....1828 Foundations....1829 Taxonomy of Human Factors....1829 Integrating Human Factors in Crowdsourcing....1831 Key Applications....1832 Future Directions....1832 Recommended Reading....1832 Human-Centered Computing: Application to Multimedia....1833 Synonyms....1833 Definition....1833 Historical Background....1834 Foundations....1835 Key Applications....1835 Ambient Intelligence and Personal Spaces....1836 Ubiquitous Computing....1836 Data Analysis and Data Interaction....1836 Virtual Environments....1836 Art....1836 Persons with Disabilities....1837 Other Applications....1837 Cross-References....1837 Recommended Reading....1837 Human-Computer Interaction....1838 Synonyms....1838 Definition....1838 Historical Background....1838 Foundations....1839 Usability....1839 Observation and Empirical Data....1839 Design and Methodology....1839 Representation and Analysis....1840 Implementation and User Interface Architecture....1841 Key Applications....1841 Future Directions....1841 Cross-References....1842 Recommended Reading....1842 Hypertexts....1843 Synonyms....1843 Definition....1843 Key Points....1843 Cross-References....1843 Recommended Reading....1843 I....1844 I/O Model of Computation....1844 Synonyms....1844 Definition....1844 Key Points....1844 Cross-References....1845 Recommended Reading....1845 Icon....1845 Synonyms....1845 Definition....1845 Key Points....1845 Cross-References....1846 Recommended Reading....1846 Iconic Displays....1846 Synonyms....1846 Definition....1846 Historical Background....1846 Foundations....1847 Perceptual Foundations....1847 Iconographics....1847 Stick Figure Icons....1848 Color Icons....1850 Kinetic Displays and Moxels....1850 Key Applications....1852 Data Sets....1853 Cross-References....1853 Recommended Reading....1853 Image....1853 Synonyms....1853 Definition....1854 Historical Background....1854 Foundations....1855 Image Acquisition....1855 Image Representation....1856 Image Processing and Analysis....1856 Computer Vision....1856 Image Synthesis....1857 Computer Graphics....1857 Image-Based Rendering....1858 Image Indexing and Retrieval....1858 Key Applications....1859 Cross-References....1859 Recommended Reading....1859 Image Content Modeling....1860 Synonyms....1860 Definition....1860 Historical Background....1860 Scientific Fundamentals....1862 Key Applications....1864 Cross-References....1864 Recommended Reading....1864 Image Database....1864 Synonyms....1864 Definition....1864 Historical Background....1865 Scientific Fundamentals....1865 Image Database Schema....1866 Index Structures....1866 Query Optimization....1867 Database Extensions to Support Images....1867 Standardized Query Extension for Multimedia: SQL/MM and JPSearch....1868 Key Applications....1868 Surveillance Systems....1868 Medical Diagnosis Supporting Systems....1868 Web Search....1869 Cross-References....1869 Recommended Reading....1869 Image Management for Biological Data....1869 Synonyms....1869 Definition....1869 Historical Background....1869 Foundations....1870 Content-Based Similarity Search....1870 Summarization....1870 Key Applications....1870 Electronic Notebook....1870 Sharing and Exploration....1871 Analysis....1872 Future Directions....1872 Cross-References....1872 Recommended Reading....1873 Image Metadata....1873 Synonyms....1873 Definition....1873 Historical Background....1874 Foundations....1875 Content Description Based on Invariant Features....1876 Content Description Based on Semantic Features....1876 Interpretation of Features....1877 Image Interpretation Based on High-Level Semantic Metadata....1878 Dublin Core [18]....1878 MPEG-7 [12]....1878 The W3c's Incubator Group [20]....1879 Key Applications....1879 Future Directions....1880 Cross-References....1880 Recommended Reading....1880 Image Querying....1881 Synonyms....1881 Definition....1881 Historical Background....1882 Foundations....1883 Matching Type....1883 Ranking Model....1884 Key Applications....1885 Cross-References....1886 Recommended Reading....1886 Image Representation....1886 Synonyms....1886 Definition....1886 Historical Background....1887 Foundations....1887 Basics of Image Representation....1887 Image Compression....1888 Run-Length Encoding....1888 Huffman Coding....1888 LZW Coding....1889 JPEG Compression....1889 File Formats....1889 Metadata Representation....1890 Image Content Representation....1891 Key Applications....1891 Future Directions....1892 Cross-References....1892 Recommended Reading....1892 Image Retrieval and Relevance Feedback....1893 Definition....1893 Historical Background....1893 Scientific Fundamentals....1893 Relevance Feedback Methods....1894 Learners....1894 Selection Criteria....1895 Temporal Structure of the Session....1896 Evaluation of Relevance Feedback in Image Retrieval....1896 Key Applications....1897 Future Directions....1897 Cross-References....1897 Recommended Reading....1898 Image Segmentation....1898 Synonyms....1898 Definition....1898 Historical Background....1898 Foundations....1899 Thresholding....1899 Object (Component) Labeling....1900 Locating Object Contours by the Snake Model....1900 The Traditional Snake Model....1900 The Improved Snake Model....1901 The Gravitation External Force Field and the Greedy Algorithm....1902 Experimental Results....1902 Automatic Seeded Region Growing....1902 Overview of the Improved Seeded Region Growing Algorithm....1903 The Method for Automatic Seed Selection....1903 The Segmentation Algorithm....1905 Key Applications....1905 Cross-References....1905 Recommended Reading....1905 Image Similarity....1906 Synonyms....1906 Definition....1906 Historical Background....1906 Foundations....1907 Image Descriptors....1907 Similarity Measures....1908 Key Applications....1910 Content-Based Multimedia Information Retrieval/Multimedia Database....1910 Object Recognition....1910 Medical/Satellite/Surveillance Applications....1910 Future Directions....1911 Cross-References....1911 Recommended Reading....1911 Implication of Constraints....1911 Synonyms....1911 Definition....1911 Historical Background....1912 Foundations....1912 Constraints (Data Dependencies)....1912 Unrestricted Implication Versus Finite Implication....1913 Implication Versus Satisfiability....1913 Finite Axiomatizability....1914 Complexity of Implication Analyses....1915 View Dependencies....1916 Key Applications....1916 Future Directions....1916 Cross-References....1916 Recommended Reading....1917 Implications of Genomics for Clinical Informatics....1917 Synonyms....1917 Definition....1917 Historical Background....1917 Foundations....1918 Integrating Genetic Data into the Clinical Record....1918 Key Applications....1918 Laboratory Information Management Systems for Genetic Laboratories....1918 Knowledgebases and Reporting Systems for Genetic Laboratories....1919 Integrated Clinical and Genetic Medical Record....1920 Clinical Decision Support....1920 Cross-References....1921 Recommended Reading....1921 Implicit Event....1922 Definition....1922 Key Points....1922 Cross-References....1922 Incomplete Information....1922 Synonyms....1922 Definition....1922 Historical Background....1923 Foundations....1924 Key Applications....1926 Future Directions....1927 Recommended Reading....1928 Inconsistent Databases....1928 Definition....1928 Historical Background....1928 Foundations....1928 Key Applications....1932 Future Directions....1932 Cross-References....1932 Recommended Reading....1932 Incremental Computation of Queries....1933 Synonyms....1933 Definition....1933 Historical Background....1933 Foundations....1934 Incremental Computation of Relational-Algebra Queries....1934 Incremental Computation of Recursive Queries....1935 Key Applications....1936 Future Directions....1936 Cross-References....1936 Recommended Reading....1936 Incremental Crawling....1936 Synonyms....1936 Definition....1937 Historical Background....1937 Foundations....1937 Metrics for Incremental Crawling....1938 Incentives and Cooperation....1938 Cache Consistency....1939 Resource Management....1939 Key Applications....1940 Future Directions....1940 Experimental Results....1940 Cross-References....1940 Recommended Reading....1940 Incremental Maintenance of Views with Aggregates....1941 Definition....1941 Historical Background....1941 Foundations....1941 Cross-References....1945 Recommended Reading....1945 Index Creation and File Structures....1945 Synonyms....1945 Definition....1945 Historical Background....1945 Foundations....1946 Key Applications....1947 Cross-References....1947 Recommended Reading....1948 Index Join....1948 Synonyms....1948 Definition....1948 Key Points....1948 Cross-References....1948 Recommended Reading....1948 Index Structures for Biological Sequences....1948 Definition....1948 Historical Background....1949 Foundations....1949 Hash Tables....1949 Suffix Trees....1950 Suffix Arrays....1950 Reference-Based Indexing....1950 Vector Space Indexing....1952 Key Applications....1953 Data Sets....1953 Cross-References....1953 Recommended Reading....1953 Index Tuning....1954 Definition....1954 Historical Background....1954 Foundations....1954 Key Applications....1956 Experimental Results....1956 Covering Experiment....1956 URL to Code and Data Sets....1956 Cross-References....1956 Recommended Reading....1956 Indexed Sequential Access Method....1957 Synonyms....1957 Definition....1957 Historical Background....1957 Foundations....1957 Key Applications....1959 Cross-References....1960 Recommended Reading....1960 Indexing and Similarity Search....1960 Synonyms....1960 Definition....1960 Historical Background....1960 Foundations....1961 Key Applications....1961 R-Trees....1961 VP-Trees....1962 Cross-References....1963 Recommended Reading....1963 Indexing Compressed Text....1964 Synonyms....1964 Definition....1964 Historical Background....1964 Foundations....1965 The FM-Index Family....1966 Other Compressed Indexes....1969 Key Applications....1969 Future Directions....1969 Experimental Results....1970 Data Sets....1970 URL to Code....1970 Cross-References....1970 Recommended Reading....1970 Indexing Historical Spatiotemporal Data....1971 Synonyms....1971 Definition....1971 Historical Background....1971 Foundations....1971 Key Applications....1973 Moving Object Databases....1973 Recommended Reading....1974 Indexing in Pub/Sub Systems....1974 Synonyms....1974 Definition....1974 Historical Background....1975 Scientific Fundamentals....1976 Future Directions....1978 Key Applications....1978 Cross-References....1979 Recommended Reading....1979 Indexing Metric Spaces....1979 Synonyms....1979 Definition....1979 Historical Background....1980 Foundations....1981 Key Applications....1981 Future Directions....1982 Experimental Results....1982 Data Sets....1983 URL to Code....1983 Cross-References....1983 Recommended Reading....1983 Indexing of Data Warehouses....1983 Synonyms....1983 Definition....1983 Historical Background....1984 Foundations....1984 Join and Star Indices....1986 Key Applications....1986 Cross-References....1987 Recommended Reading....1987 Indexing of the Current and Near-Future Positions of Moving Objects....1987 Definition....1987 Historical Background....1988 Foundations....1989 Data and Queries....1989 The Structure of the TPR-Tree....1989 Querying the TPR-Tree....1990 Updating the TPR-Tree....1990 Duality-Transformation Approach....1991 Key Applications....1991 Online, Position-Aware People, Vehicles, and Other Objects....1991 Process Monitoring....1991 Future Directions....1992 URL to Code....1992 Cross-References....1992 Recommended Reading....1992 Indexing Techniques for Multimedia Data Retrieval....1993 Synonyms....1993 Definition....1993 Historical Background....1993 Scientific Foundations....1993 Tree Structures....1994 Data Transformation....1994 Quantization....1995 Hashing....1996 Key Applications....1997 Content-Based Multimedia Retrieval....1997 Near-Duplicate Video Retrieval....1997 Automatic Multimedia Tagging....1997 Object Detection....1997 Video Tracking....1998 Cross-References....1998 Recommended Reading....1998 Indexing the Web....1999 Synonyms....1999 Definition....1999 Historical Background....1999 Foundations....2000 Introduction....2000 Data Structures to Support Automatic Indexing....2001 Challenges and Design Factors in Automatic Indexing....2001 Key Applications....2003 Cross-References....2003 Recommended Reading....2003 Indexing Uncertain Data....2003 Synonyms....2003 Definition....2004 Historical Background....2004 Foundations....2004 Key Applications....2008 Future Directions....2008 URL to Code....2009 Cross-References....2009 Recommended Reading....2009 Indexing Units of Structured Text Retrieval....2010 Synonyms....2010 Definition....2010 Historical Background....2010 Foundations....2011 Toy Story....2011 Cross-References....2014 Recommended Reading....2014 Indexing with Crowds....2014 Synonyms....2014 Definition....2014 Historical Background....2015 Indexing Data Using the Crowds....2015 Indexing the Crowds....2015 Scientific Fundamentals....2015 Indexing Data Using the Crowds....2015 Tree-Based Crowd Indexing....2016 Hash-Based Crowd Indexing....2016 Indexing the Crowds....2016 Skill-Based Worker Indexing....2016 Spatial Worker Indexing....2017 Cross-References....2017 Recommended Reading....2017 Individually Identifiable Data....2018 Synonyms....2018 Definition....2018 Key Points....2018 Cross-References....2018 Recommended Reading....2019 Inference Control in Statistical Databases....2019 Synonyms....2019 Definition....2019 Historical Background....2019 Foundations....2019 Key Applications....2021 Future Directions....2022 Cross-References....2022 Recommended Reading....2022 Information Extraction....2023 Definition....2023 Historical Background....2024 Entity Detection and Recognition....2024 Relation Detection and Recognition....2024 Event Detection and Recognition....2024 Entity Translation....2024 Foundations....2025 Pattern Matching Based IE....2025 Machine Learning Based IE....2025 Trainable Name Tagging....2026 Trainable Coreference Resolution....2026 Trainable Relation Detection....2026 Trainable Event Detection....2027 Key Applications....2027 Future Directions....2027 Experimental Results....2028 Data Sets....2028 URL to Code....2028 Cross-References....2029 Recommended Reading....2029 Information Filtering....2029 Synonyms....2029 Definition....2029 Historical Background....2030 Foundations....2030 Organization of a Filtering System....2030 Profile Building and Evolution....2031 Comparison Procedure....2031 Relevance Feedback....2032 Named Entities in Filtering....2032 Thematic Filtering Versus Event Filtering....2032 Evaluation of Filtering Systems....2032 Key Applications....2033 Cross-References....2033 Recommended Reading....2033 Information Foraging....2033 Synonyms....2033 Definition....2033 Historical Background....2034 Foundations....2034 Key Applications....2038 Engineering Models of Browser Use....2038 Novel Search and Browsing Interfaces....2038 Usability Guidelines....2038 Future Directions....2039 Cross-References....2039 Recommended Reading....2039 Information Integration....2039 Synonyms....2039 Definition....2039 Historical Background....2040 Foundations....2040 Information Integration Architecture....2040 Schema Mediation Languages....2042 Generating Schema Mappings....2043 Query Processing....2044 Related Data Management Architectures....2044 The Information Integration Industry....2045 Key Applications....2045 Future Directions....2045 Cross-References....2046 Recommended Reading....2046 Information Integration Techniques for Scientific Data....2046 Definition....2046 Historical Background....2046 Foundations....2047 Semantic Heterogeneity....2047 Role of Metadata in Managing Semantic Heterogeneity....2047 Functional Relationships....2047 Non-schematic Integration....2048 New Issues....2048 Interactive Information Integration....2048 Quality of Integration....2048 Key Applications....2048 BIRN....2048 Data Foundry....2049 GEON....2049 Cross-References....2049 Recommended Reading....2049 Information Lifecycle Management....2049 Synonyms....2049 Definition....2049 Key Points....2050 Cross-References....2050 Recommended Reading....2050 Information Loss Measures....2050 Synonyms....2050 Definition....2050 Key Points....2051 Cross-References....2052 Recommended Reading....2052 Information Navigation....2052 Synonyms....2052 Definition....2052 Key Points....2053 Recommended Reading....2054 Information Quality and Decision-Making....2054 Synonyms....2054 Definition....2054 Historical Background....2054 Foundations....2055 Key Applications....2057 Future Directions....2057 Experimental Results....2057 Cross-References....2057 Recommended Reading....2058 Information Quality Assessment....2058 Synonyms....2058 Definition....2058 Historical Background....2059 Foundations....2059 Key Applications....2061 Cross-References....2061 Recommended Reading....2061 Information Quality Policy and Strategy....2061 Synonyms....2061 Definition....2062 Historical Background....2062 Foundations....2062 Treat Information as a Product, Not By-Product....2062 Establish and Maintain Information Quality as a Part of the Business Agenda....2062 Ensure That Information Quality Policy and Procedures are Aligned with Business Strategy, Business Policy, and Business Processes....2063 Establish Clearly Defined Information Quality Roles and Responsibilities as Part of Organizational Structure....2063 Ensure Data Architecture is Aligned with Enterprise Architecture....2063 Be Proactive in Managing Changing Data Needs....2063 Have Practical Data Standards in Place....2064 Plan for and Implement Pragmatic Methods to Identify and Solve Data Quality Problems, and Have in Place a Means to Periodically Review Data Quality Practice and the Data Product....2064 Foster an Environment Conducive to Learning and Innovating with Respect to Data Quality Activities....2064 Establish a Mechanism to Resolve Disputes and Conflicts Among Different Stakeholders....2065 Key Applications....2065 Future Directions....2065 Cross-References....2066 Recommended Reading....2066 Information Quality: Managing Information as a Product....2066 Definition....2066 Historical Background....2067 Foundations....2067 The Needs of Information Consumers....2067 Processes for Producing High-Quality Information....2069 The Life Cycle of Information Products....2070 Governance Structures for Managing Information as a Product....2070 Key Applications....2071 Principle 1: Understand the IP Needs of Information Consumers....2071 Principle 2: Manage Information as a Product of a Well-Defined Production Process....2071 Principle 3: Manage Information as a Product with a Life Cycle....2072 Principle 4: Develop a Governance Structure to Manage Information Production Processes and the Resulting Information Products....2072 Future Directions....2072 Cross-References....2073 Recommended Reading....2073 Information Retrieval....2073 Synonyms....2073 Definition....2073 Historical Background....2074 Foundations....2075 Key Applications....2077 Future Directions....2077 Data Sets....2078 URL to Code....2078 Cross-References....2078 Recommended Reading....2078 Information Retrieval Models....2079 Synonyms....2079 Definition....2079 Historical Background....2079 Foundations....2079 Probabilistic Indexing....2080 Information Theoretic Models....2080 Vector Space Models....2081 Bayesian Models....2082 Probabilistic and Binary Retrieval Models....2083 Logical and Algebraic Models....2083 Key Applications....2083 Future Directions....2083 Experimental Results....2084 Data Sets....2084 Cross-References....2084 Recommended Reading....2084 Information Retrieval Operations....2084 Synonyms....2084 Definition....2085 Historical Background....2085 Foundations....2085 Experimental Results....2086 Cross-References....2087 Recommended Reading....2087 Infrastructure-as-a-Service (IaaS)....2087 Synonyms....2087 Definition....2088 Overview....2088 Cross-References....2088 References....2088 Initiative for the Evaluation of XML Retrieval....2088 Synonyms....2088 Definition....2088 Historical Background....2089 Foundations....2089 Key Applications....2094 Data Sets....2094 URL to Code....2095 Cross-References....2095 Recommended Reading....2096 Initiator....2096 Synonyms....2096 Definition....2096 Key Points....2096 Cross-References....2096 In-Network Query Processing....2097 Synonyms....2097 Definition....2097 Historical Background....2097 Foundations....2098 Network Formation and Communication....2098 Query Language and Data Model....2098 In-Network Processing of Aggregates....2099 Classes of Aggregates....2101 In-Network Processing of Joins....2101 Key Applications....2102 Cross-References....2102 Recommended Reading....2102 Integrated DB and IR Approaches....2102 Synonyms....2102 Definition....2103 Historical Background....2103 Foundations....2103 Querying Semi-structured Data with IR Support....2103 Query Processing for Semi-structured Text Retrieval....2105 Support for XML-IR in Commercial Database Systems....2105 Key Applications....2105 Cross-References....2105 Recommended Reading....2106 Integration of Rules and Ontologies....2106 Definition....2106 Historical Background....2106 Foundations....2107 Shortcomings of OWL....2107 Rule Languages for Integration....2107 Approaches to Integration....2108 Key Applications....2110 URL to Code....2111 Cross-References....2111 Recommended Reading....2111 Intelligent Storage Systems....2112 Synonyms....2112 Definition....2112 Historical Background....2112 Foundations....2112 Key Applications....2113 Cross-References....2113 Recommended Reading....2113 Interactive Analytics in Social Media....2114 Synonyms....2114 Definition....2114 Historical Background....2114 Foundations....2115 Key Applications....2116 Future Directions....2116 Recommended Reading....2116 Interface....2116 Definition....2116 Historical Background....2117 Foundations....2117 Interfaces and Classes....2117 Protection....2118 Remote Interfaces....2118 Contents....2118 Components....2119 Key Applications....2119 Future Directions....2120 Cross-References....2120 Recommended Reading....2120 Interface Engines in Healthcare....2121 Synonyms....2121 Definition....2121 Historical Background....2121 Foundations....2123 Key Applications....2124 Cross-References....2124 Recommended Reading....2124 Interoperability in Data Warehouses....2124 Synonyms....2124 Definition....2124 Historical Background....2125 Foundations....2125 Standards....2126 Conflicts....2126 Integration Techniques....2127 Key Applications....2128 Future Directions....2128 Experimental Results....2128 Cross-References....2128 Recommended Reading....2128 Interoperation of NLP-Based Systems with Clinical Databases....2129 Synonyms....2129 Definition....2129 Key Points....2130 Cross-References....2130 Recommended Reading....2130 Inter-operator Parallelism....2131 Synonyms....2131 Definition....2131 Key Points....2132 Cross-References....2132 Inter-query Parallelism....2132 Synonyms....2132 Definition....2132 Key Points....2132 Cross-References....2133 Recommended Reading....2133 Intra-operator Parallelism....2133 Synonyms....2133 Definition....2133 Key Points....2133 Cross-References....2133 Intra-query Parallelism....2133 Synonyms....2133 Definition....2133 Key Points....2134 Cross-References....2134 Recommended Reading....2134 Intrusion Detection Technology....2134 Definition....2134 Historical Background....2134 Scientific Fundamentals and Key Applications....2135 Types of Attacks....2135 Detection Methodologies....2136 Future Directions....2137 Recommended Reading....2137 Inverse Document Frequency....2139 Synonyms....2139 Definition....2139 Key Points....2140 Cross-References....2140 Recommended Reading....2140 Inverted Files....2140 Synonyms....2140 Definition....2140 Historical Background....2140 Foundations....2141 Building an Inverted File....2141 Compression....2142 Updating Operations....2143 Query Processing....2143 Key Applications....2144 Cross-References....2144 Recommended Reading....2144 IP Storage....2144 Definition....2144 Key Points....2144 Cross-References....2145 Recommended Reading....2145 Iterator....2145 Synonyms....2145 Definition....2145 Key Points....2145 Cross-References....2146 Recommended Reading....2146 J....2147 Java Database Connectivity....2147 Synonyms....2147 Definition....2147 Key Points....2147 Cross-References....2148 Recommended Reading....2148 Java Enterprise Edition....2148 Synonyms....2148 Definition....2148 Key Points....2148 Cross-References....2150 Recommended Reading....2150 Java Metadata Facility....2150 Synonyms....2150 Definition....2150 Key Points....2150 Cross-References....2151 Recommended Reading....2151 Join....2151 Definition....2151 Key Points....2151 Cross-References....2152 Join Dependency....2152 Synonyms....2152 Definition....2152 Key Points....2152 Cross-References....2152 Recommended Reading....2153 Join Index....2153 Definition....2153 Key Points....2153 Cross-References....2153 Recommended Reading....2153 Join Order....2153 Synonyms....2153 Definition....2153 Key Points....2154 Cross-References....2154 Recommended Reading....2154 K....2155 k-Anonymity....2155 Synonyms....2155 Definition....2155 Key Points....2155 Cross-References....2155 Recommended Reading....2156 Karp-Luby Sampling....2156 Definition....2156 Main Text....2156 Cross-References....2157 Recommended Reading....2157 KDD Pipeline....2157 Synonyms....2157 Definition....2157 Selection....2157 Preprocessing....2157 Transformation....2157 Data Mining....2158 Evaluation and Interpretation....2158 Key Points....2158 Cross-References....2158 Recommended Reading....2158 Key....2159 Synonyms....2159 Definition....2159 Key Points....2159 Cross-References....2160 K-Means and K-Medoids....2160 Synonyms....2160 Definitions....2160 K-Means....2160 K-Medoids....2160 Key Points....2160 K-Means....2160 K-Medoids....2161 Cross-References....2161 Recommended Reading....2161 L....2162 Language Models....2162 Synonyms....2162 Definition....2162 Historical Background....2162 Foundations....2163 Implementation....2163 Document Priors....2163 Document Generation Models....2164 Translation Models....2164 Aspect Models....2165 Key Applications....2165 Cross-References....2165 Recommended Reading....2165 Languages for Web Data Extraction....2166 Synonyms....2166 Definition....2166 Historical Background....2167 Foundations....2168 Access....2168 Extract....2169 Process....2170 Output....2171 Key Applications....2171 Future Directions....2172 URL to Code....2172 Cross-References....2172 Recommended Reading....2173 Learning Distance Measures....2173 Synonyms....2173 Definition....2173 Historical Background....2174 Foundations....2174 Statistical Approach....2174 Challenges....2175 Adaptive Metric Techniques....2176 Adaptive Metric Nearest Neighbor Classification....2176 Large Margin Nearest Neighbor Classifiers....2176 Adaptive Metrics for Clustering and Semi-Supervised Clustering....2177 Key Applications....2177 Cross-References....2178 Recommended Reading....2178 Lexical Analysis of Textual Data....2178 Synonyms....2178 Definitions....2178 Historical Background....2178 Foundations....2179 Lexical Analysis in Text Processing....2179 Lexical Extraction....2179 Lookup....2180 Use of the Output....2180 Types of Lexicon....2181 Word Lists and Stoplists....2181 Indexes and Inverted Files....2181 Machine Readable Dictionaries....2181 Thesauruses....2181 Construction of Lexicons....2182 Key Applications....2183 Data Sets....2183 URL to Code....2183 Cross-References....2183 Recommended Reading....2183 Licensing and Contracting Issues in Databases....2183 Synonyms....2183 Definition....2184 Historical Background....2184 Foundations....2184 Key Applications....2185 Cross-References....2185 Recommended Reading....2185 Lifespan....2186 Synonyms....2186 Definition....2186 Key Points....2186 Cross-References....2186 Recommended Reading....2186 Lightweight Ontologies....2186 Synonyms....2186 Definition....2186 Historical Background....2187 Foundations....2188 Types of Lightweight Ontologies....2188 From Informal to Formal Lightweight Ontologies....2190 Key Applications....2191 Document Classification....2192 Semantic Search....2192 Data Integration....2192 Future Directions....2192 Experimental Results....2193 Data Sets....2193 Recommended Reading....2193 Linear Hashing....2194 Definition....2194 Historical Background....2194 Foundations....2194 Initial Layout....2194 Bucket Split....2194 Round and Hash Function Advancement....2195 Component Summary and Search Scheme....2196 Variations....2196 Key Applications....2196 Cross-References....2196 Recommended Reading....2197 Linear Regression....2197 Definition....2197 Key Points....2197 References....2197 Linked Open Data....2197 Synonyms....2197 Definition....2197 Historical Background....2198 Scientific Fundamentals....2198 Key Applications....2201 Data Sets....2201 Cross-References....2201 Recommended Reading....2201 Linking and Brushing....2202 Synonyms....2202 Definition....2202 Historical Background....2202 Foundations....2202 Key Applications....2204 URL to Code....2205 Cross-References....2205 Recommended Reading....2205 Load Balancing in Peer-to-Peer Overlay Networks....2206 Definition....2206 Historical Background....2206 Foundations....2207 Approaches for Balancing Storage Load....2208 Distributed Hash Tables (DHTs)....2208 Beyond DHTs....2209 Approaches for Balancing Requests Related Load....2211 Key Applications....2211 Future Directions....2211 Cross-References....2212 Recommended Reading....2212 Load Shedding....2212 Definition....2212 Historical Background....2213 Foundations....2213 Key Applications....2216 Future Directions....2216 Cross-References....2216 Recommended Reading....2216 LOC METS....2217 Synonyms....2217 Definition....2217 Key Points....2217 Cross-References....2218 Recommended Reading....2218 Locality....2218 Cross-References....2218 Locality of Queries....2218 Synonyms....2218 Definition....2219 Key Points....2219 Cross-References....2219 Recommended Reading....2219 Location Management in Mobile Environments....2220 Synonyms....2220 Definition....2220 Location Update Strategy in the LA-Based Approach....2220 Elements and Architecture of GSM....2220 Location Update....2221 Main Text....2221 A Critique of the Conventional Approach and Alternatives....2221 Recommended Reading....2223 Location-Based Recommendation....2224 Synonyms....2224 Definition....2224 Historical Background....2224 Scientific Fundamentals....2225 Applications....2227 Stand-Alone Location Recommendation....2227 Travel Route Recommendation....2227 Location-Based Social Media Recommendation....2227 Activity Recommendation....2227 Location-Based Friend Recommendation....2227 Data Sets....2227 Recommended Reading....2228 Location-Based Services....2229 Synonyms....2229 Definition....2229 Historical Background....2229 Foundations....2230 Location-Aware Technologies....2230 Locational and Spatial Data Management....2230 Middleware, Open Standards and Interoperability....2231 Locational Privacy....2231 Key Applications....2231 Recommended Reading....2232 Locking Granularity and Lock Types....2232 Synonyms....2232 Definition....2232 Key Points....2233 Cross-References....2234 Recommended Reading....2234 Logging and Recovery....2234 Synonyms....2234 Definition....2234 Key Points....2234 Cross-References....2235 Recommended Reading....2235 Logging/Recovery Subsystem....2236 Synonyms....2236 Definition....2236 Key Points....2236 Cross-References....2237 Recommended Reading....2237 Logical and Physical Data Independence....2237 Synonyms....2237 Definition....2237 Historical Background....2237 Scientific Fundamentals....2238 Key Applications....2238 Cross-References....2238 Recommended Reading....2238 Logical Database Design: From Conceptual to Logical Schema....2238 Synonyms....2238 Definition....2238 Historical Background....2238 Foundations....2239 The Basic E2R Mapping....2239 Refinements....2240 Table Merging....2240 Table Partitioning....2241 Mapping from Non-ER Conceptual Schemas....2241 Key Applications....2241 Database Design....2241 Future Directions....2242 URL to Code....2242 Cross-References....2242 Recommended Reading....2242 Logical Document Structure....2242 Definition....2242 Key Points....2242 Cross-References....2243 Logical Foundations of Web Data Extraction....2243 Definition....2243 Historical Background....2243 Foundations....2243 Information Extraction Functions and Wrappers....2243 Tree Structures....2244 Monadic Datalog....2244 Key Application....2246 Cross-References....2246 Recommended Reading....2246 Logical Models of Information Retrieval....2246 Definition....2246 Historical Background....2247 Foundations....2248 Logical Models....2248 Logical-Uncertainty Models....2250 Meta-Models....2252 Key Applications....2252 Future Directions....2252 Cross-References....2252 Recommended Reading....2253 Logical Unit Number....2253 Synonyms....2253 Definition....2253 Key Points....2253 Cross-References....2253 Logical Unit Number Mapping....2254 Synonyms....2254 Definition....2254 Key Points....2254 Cross-References....2254 Logical Volume Manager....2254 Synonyms....2254 Definition....2254 Key Points....2254 Cross-References....2255 Log-Linear Regression....2255 Definition....2255 Key Points....2255 Cross-References....2255 Recommended Reading....2256 Loop....2256 Synonyms....2256 Definition....2256 Key Points....2256 Cross-References....2256 Loose Coupling....2256 Synonyms....2256 Definition....2256 Key Points....2256 Cross-References....2257 Recommended Reading....2257 M....2258 Machine Learning in Computational Biology....2258 Synonyms....2258 Definition....2258 Historical Background....2258 Foundations....2259 Key Applications....2261 Future Directions....2262 Cross-References....2262 Recommended Reading....2262 Main Memory....2263 Synonyms....2263 Definition....2263 Key Points....2263 Cross-References....2264 Main Memory DBMS....2265 Synonyms....2265 Definition....2265 Key Points....2265 Cross-References....2265 Recommended Reading....2265 Maintenance of Materialized Views with Outer-Joins....2266 Definition....2266 Historical Background....2266 Foundations....2266 Join-Disjunctive Normal Form....2266 The Subsumption Graph....2267 Maintenance Procedure....2268 Computing the Primary Delta....2269 Computing the Secondary Delta....2269 Summary....2270 Key Applications....2270 Cross-References....2270 Recommended Reading....2270 Maintenance of Recursive Views....2271 Synonyms....2271 Definition....2271 Historical Background....2271 Foundations....2272 Recursive View Definition....2272 Evaluation of Recursive Queries....2273 Incremental Evaluation of Recursive Views....2274 Key Applications....2276 Cross-References....2276 Recommended Reading....2277 Managing Compressed Structured Text....2277 Synonyms....2277 Definition....2277 Historical Background....2277 Scientific Fundamentals....2278 Compression of Structured Text....2278 Navigating and Searching in Compressed Form....2279 Succinct Encodings for Labeled Trees....2280 Integrating Indexing and Compression....2282 Key Applications....2284 Future Directions....2284 Experimental Results....2284 Url to Code....2284 Cross-References....2284 Recommended Reading....2284 Managing Data Integration Uncertainty....2285 Synonyms....2285 Definition....2285 Historical Background....2285 Scientific Fundamentals....2286 Key Applications....2288 Dataspace Systems....2288 Probabilistic Data Warehousing....2288 Probabilistic Knowledge Base Construction....2288 Cross-References....2288 Recommended Reading....2288 Managing Probabilistic Entity Extraction....2288 Synonyms....2288 Definition....2288 Historical Background....2289 Foundations....2289 Extracting Probabilistic Entities....2289 Probabilistic Data Model....2290 Data Model for Probabilistic Entity Extraction....2290 Probabilistic Entity Table....2291 Querying Probabilistic Entities via Inference....2292 Key Applications....2293 Cross-References....2293 Recommended Reading....2293 Mandatory Access Control....2293 Synonyms....2293 Definition....2294 Key Point....2294 Cross-References....2294 Recommended Reading....2294 MANET Databases....2295 Synonyms....2295 Definition....2295 Historical Background....2295 Pedestrians Projects....2296 Vehicular Projects....2297 Foundations....2297 Key Applications....2299 Social Networks....2299 Emergency Response, Homeland Security, and the Military....2299 Airport Applications....2299 Mobile E-Commerce....2300 Transportation Safety and Efficiency....2300 Future Directions....2300 Recommended Reading....2301 MAP....2301 Synonyms....2301 Definition....2301 Key Points....2302 Cross-References....2302 Recommended Reading....2302 Map Matching....2302 Synonyms....2302 Definition....2302 Historical Background....2303 Foundations....2303 Key Applications....2306 Future Directions....2306 Cross-References....2306 Recommended Reading....2306 MapReduce....2307 Scientific Fundamentals....2307 Definition....2307 Historical Background....2307 Foundations....2308 Key Applications....2310 URL to Code....2310 Recommended Reading....2310 Markup Language....2311 Definition....2311 Key Points....2311 Cross-References....2311 MashUp....2311 Definition....2311 Key Points....2311 Cross-References....2312 Massive Array of Idle Disks....2312 Synonyms....2312 Definition....2312 Key Points....2312 Cross-References....2313 Recommended Reading....2313 Matrix Masking....2313 Synonyms....2313 Definition....2313 Key Points....2313 Cross-References....2313 Recommended Reading....2313 Max-Pattern Mining....2314 Synonyms....2314 Definition....2314 Historical Background....2314 Scientific Fundamentals....2317 Key Applications....2317 Experimental Results....2317 Data Sets....2317 URL to Code....2317 Cross-References....2317 Recommended Reading....2317 Mean Reciprocal Rank....2318 Synonyms....2318 Definition....2318 Key Points....2318 Cross-References....2318 Measure....2318 Synonyms....2318 Definition....2318 Key Points....2319 Cross-References....2319 Recommended Reading....2320 Mediation....2320 Synonyms....2320 Definition....2320 Historical Background....2320 Foundations....2320 Key Applications....2322 Cross-References....2322 Recommended Reading....2322 Membership Query....2323 Synonyms....2323 Definition....2323 Key Points....2323 Cross-References....2323 Memory Hierarchy....2323 Synonyms....2323 Definition....2323 Historical Background....2324 Foundations....2325 Memory- and Cache-Architectures....2325 Memory Access Costs....2328 Latency....2328 Bandwidth....2328 Address Translation....2329 Unified Hardware Model....2329 Key Applications....2330 URL to Code....2330 Cross-References....2330 Recommended Reading....2330 Memory Locality....2330 Synonyms....2330 Definition....2330 Key Point....2331 Cross-References....2331 Recommended Reading....2331 Merkle Trees....2332 Synonyms....2332 Definition....2332 Key Point....2332 Cross-References....2333 Recommended Reading....2333 Message Authentication Codes....2333 Synonyms....2333 Definition....2333 Key Points....2333 Cross-References....2333 Recommended Reading....2333 Message Queuing Systems....2333 Synonyms....2333 Definition....2334 Key Points....2334 Cross-References....2334 Recommended Reading....2334 Meta Data Repository....2334 Synonyms....2334 Definition....2335 Historical Background....2335 Foundations....2336 Requirements....2336 Architecture....2336 Systems....2337 Key Applications....2337 Future Directions....2338 Cross-References....2338 Recommended Reading....2338 Meta Object Facility....2339 Synonyms....2339 Definition....2339 Key Points....2339 Cross-References....2340 Recommended Reading....2340 Metadata....2340 Definition....2340 Key Points....2341 Cross-References....2341 Recommended Reading....2341 Metadata Interchange Specification....2341 Synonyms....2341 Definition....2341 Key Points....2341 Cross-References....2342 Recommented Reading....2342 Metadata Registry, ISO/IEC 11179....2343 Synonyms....2343 Definition....2343 Historical Background....2343 Foundations....2343 Part 1: Framework....2343 Part 2: Classification....2344 Part 3: Registry Metamodel and Basic Attributes....2344 Part 4: Formulation of Data Definitions....2345 Part 5: Naming and Identification Principles....2345 Part 6: Registration....2345 Key Applications....2345 Cross-References....2346 Recommended Reading....2346 Metamodel....2346 Synonyms....2346 Definition....2346 Historical Background....2347 Foundations....2347 Key Applications....2348 Future Directions....2348 Cross-References....2349 Recommended Reading....2349 Metasearch Engines....2349 Synonyms....2349 Definition....2349 Historical Background....2349 Scientific Fundamentals....2350 Result Merging....2350 Search Engine Selection....2351 Automatic Search Engine Connection....2352 Automatic Search Result Extraction....2352 Key Applications....2353 Future Directions....2353 Cross-References....2353 Recommended Reading....2354 Metric Space....2354 Synonyms....2354 Definition....2354 Key Points....2355 Cross-References....2355 Recommended Reading....2355 Microaggregation....2355 Definition....2355 Key Points....2356 Cross-References....2356 Recommended Reading....2356 Microbenchmark....2356 Definition....2356 Key Points....2357 Cross-References....2357 Recommended Reading....2357 Microdata....2357 Synonyms....2357 Definition....2357 Key Points....2357 Cross-References....2358 Recommended Reading....2358 Microdata Rounding....2358 Synonyms....2358 Definition....2358 Key Points....2358 Cross-References....2358 Recommended Reading....2358 Middleware Support for Database Replication and Caching....2358 Definition....2358 Historical Background....2359 Foundations....2359 Shared Disk Versus Shared Nothing....2359 Master/Slave Versus Multi-master....2359 Middleware Design....2360 Concurrency Control....2360 Statement Replication Versus Transaction Replication....2361 High Availability....2362 Load Balancing....2363 Caching....2363 Key Applications....2363 Future Directions....2364 URL to Code....2364 Cross-References....2364 Recommended Reading....2364 Middleware Support for Precise Failure Semantics....2365 Definition....2365 Historical Background....2365 Foundations....2365 System Model....2366 X-Able Histories....2367 Client-Service Consistency....2369 X-Able Services....2369 Key Applications....2370 Recommended Reading....2370 Mining of Chemical Data....2370 Definition....2370 Historical Background....2370 Foundations....2371 Key Applications....2372 Experimental Results....2372 Data Sets....2372 Cross-References....2373 Recommended Reading....2373 Mobile Database....2373 Definition....2373 Key Points....2373 Recommended Reading....2374 Mobile Interfaces....2374 Synonyms....2374 Definition....2374 Historical Background....2374 Foundations....2376 Mobile Interface for Specific Devices....2376 Multi Target Applications....2376 Key Applications....2377 Future Directions....2377 Cross-References....2377 Recommended Reading....2377 Mobile Resource Search....2378 Synonyms....2378 Definition....2378 Historical Background....2378 Scientific Fundamentals....2379 Key Applications....2380 Searching Available Parking Spaces....2380 Searching Taxi Cabs/Taxi Customers....2381 Searching Vehicles and People for Ridesharing....2381 Searching Charging Stations for Electric Vehicles....2381 Searching Competition-Free Resources....2382 Future Directions....2382 Cross-References....2383 Recommended Reading....2383 Mobile Sensor Network Data Management....2384 Synonyms....2384 Definition....2384 Historical Background....2384 Foundations....2385 Key Applications....2387 Cross-References....2388 Recommended Reading....2388 Model Management....2389 Definition....2389 Historical Background....2390 Foundations....2390 Schema Matching....2390 Model Transformation....2391 Generic Metamodel....2391 Schema Integration....2392 Mappings....2392 Model Management Systems....2392 Key Applications....2393 Future Directions....2393 Cross-References....2393 Recommended Reading....2394 Model-Based Querying in Sensor Networks....2394 Synonyms....2394 Definition....2394 Historical Background....2395 Foundations....2395 Model....2396 Query Planning and Execution....2397 Example....2398 Key Applications....2398 Future Directions....2399 Cross-References....2399 Recommended Reading....2399 Monotone Constraints....2400 Synonyms....2400 Definition....2400 Key Points....2400 Cross-References....2400 Recommended Reading....2400 Monte Carlo Methods for Uncertain Data....2400 Synonyms....2400 Definition....2401 Historical Background....2401 Scientific Fundamentals....2402 PC-Tables and Karp-Luby Sampling....2402 PGMs and MCMC....2403 Generative Uncertainty Models: MCDB, PIP, and SimSQL....2404 Uncertain Graph Data and Related Models....2405 Key Applications....2406 Future Directions....2406 Url to Code....2406 Cross-References....2407 Recommended Reading....2407 Moving Object....2408 Synonyms....2408 Definition....2408 Key Points....2408 Cross-References....2408 Recommended Reading....2408 Moving Objects Databases and Tracking....2408 Synonyms....2408 Definition....2408 Historical Background....2409 Scientific Fundamentals....2409 Modeling and Querying Current Movement (Tracking)....2409 Modeling and Querying History of Movement....2411 Related Issues....2412 Uncertainty....2412 Movement in Networks....2413 Spatio-Temporal Indexing....2413 Query Processing for Continuous/Location-Based Queries....2413 Spatiotemporal Aggregation and Selectivity Estimation....2413 Key Applications....2413 Future Directions....2414 Experimental Results....2414 Data Sets....2414 URL to Code....2414 Cross-References....2414 Recommended Reading....2415 Multi-data Center Replication Protocols....2415 Synonyms....2415 Definition....2415 Historical Background....2415 Scientific Fundamentals....2416 Synchronous Replication....2417 Asynchronous Replication....2418 Key Applications....2420 Cross-References....2421 Recommended Reading....2421 Multi-datacenter Consistency Properties....2421 Synonyms....2421 Definition....2422 Historical Background....2422 Scientific Fundamentals....2422 Coordination and Serializability....2422 Beyond Serializability....2423 i.) Eventual Consistency....2423 ii.) Leverage Full Application Semantics....2423 iii.) Exploit More Limited Application Information....2424 WAN Serializability....2425 Key Characteristics....2426 Key Applications....2426 Future Directions....2427 Recommended Reading....2427 Multidimensional Data Formats....2428 Definition....2428 Key Points....2428 Cross-References....2429 Recommended Reading....2429 Multidimensional Modeling....2429 Synonyms....2429 Definition....2429 Historical Background....2429 Scientific Fundamentals....2430 Data Cubes....2430 Dimensions....2431 Facts....2432 Measures....2433 The Modeling Process....2433 Complex Multidimensional Modeling....2434 Key Applications....2436 Future Directions....2436 Cross-References....2436 Recommended Reading....2437 Multidimensional Scaling....2437 Synonyms....2437 Definition....2437 Key Points....2438 Cross-References....2438 Recommended Reading....2438 Multilevel Modeling....2438 Synonyms....2438 Definition....2438 Historical Background....2439 Scientific Fundamentals....2440 Background from Two-Level Modeling....2440 Core Multilevel Modeling Patterns....2442 Class and Metaclass Facets of Clabjects....2443 Additional Multilevel Modeling Patterns....2444 Key Applications....2444 Cross-References....2445 Recommended Reading....2445 Multilevel Recovery and the ARIES Algorithm....2445 Definition....2445 Historical Background....2446 Foundations....2446 Future Directions....2450 Cross-References....2450 Recommended Reading....2450 Multilevel Secure Database Management System....2450 Synonyms....2450 Definition....2450 Historical Background....2451 Foundations....2451 Key Applications....2453 Future Directions....2453 Cross-References....2454 Recommended Reading....2454 Multilevel Transactions and Object-Model Transactions....2454 Synonyms....2454 Definition....2454 Historical Background....2454 Foundations....2455 Future Directions....2459 Cross-References....2459 Recommended Reading....2459 Multimedia Data....2460 Synonyms....2460 Definition....2460 Historical Background....2460 Foundations....2461 Types and Semantics....2461 Sequence and Order....2461 Size....2462 Accessing Multimedia Data....2462 Presentation....2462 Key Applications....2462 Future Directions....2463 Cross-References....2463 Recommended Reading....2463 Multimedia Data Buffering....2463 Definition....2463 Historical Background....2463 Foundations....2464 Buffer Replacement....2464 The BASIC Buffer Replacement Algorithm....2464 The DISTANCE Buffer Replacement Algorithm....2465 Buffer Sharing....2465 Key Applications....2467 Cross-References....2467 Recommended Reading....2467 Multimedia Data Indexing....2468 Synonyms....2468 Definition....2468 Historical Background....2468 Foundations....2468 Filter and Refine....2469 The Need for Approximate Features....2470 Metric Indexing....2470 Ad Hoc Solutions....2471 Key Applications....2472 Future Directions....2472 Cross-References....2472 Recommended Reading....2472 Multimedia Data Querying....2473 Definition....2473 Historical Background....2473 Foundations....2475 Feature Representations....2475 Fuzzy and Probabilistic Models....2476 Dimensionality Reduction and Feature Selection....2480 Tensors and Tensor Decomposition....2480 Multi-Dimensional Indexing....2481 Clustering....2481 Supervised Learning/Classification....2481 Relevance Feedback and Collaborative Filtering....2481 Key Applications....2482 Future Directions....2482 Cross-References....2483 Recommended Reading....2483 Multimedia Data Storage....2484 Definition....2484 Historical Background....2484 Foundations....2484 Hiccup-Free Display....2484 FIXB and VARB....2485 RP, MTP, and MVP....2486 Data Placement Across Disk Drivers....2486 Key Applications....2486 Cross-References....2487 Recommended Reading....2487 Multimedia Databases....2487 Synonyms....2487 Definition....2487 Historical Background....2488 Foundations....2489 Data Analysis and Feature Extraction....2489 Domain Knowledge and Interpretation....2489 Interaction and User Interface....2489 Storage, Matching, and Indexing....2490 Key Applications....2490 Future Directions....2490 Cross-References....2490 Recommended Reading....2490 Multimedia Information Retrieval Model....2491 Synonyms....2491 Definition....2491 Historical Background....2491 Foundations....2492 Form-Based Multimedia Information Retrieval....2493 Semantic Content-Based Multimedia Information Retrieval....2494 Mixed Multimedia Information Retrieval....2494 Key Applications....2495 Cross-References....2495 Recommended Reading....2495 Multimedia Metadata....2495 Synonyms....2495 Definition....2496 Historical Background....2496 Foundations....2498 Media Content....2498 Layout....2498 Timing....2499 Linking....2499 Adaptivity....2499 Key Applications....2500 Cross-References....2500 Recommended Reading....2500 Multimedia Presentation Databases....2501 Synonyms....2501 Definition....2501 Historical Background....2501 Foundations....2502 Key Applications....2503 Future Directions....2503 Cross-References....2503 Recommended Reading....2503 Multimedia Resource Scheduling....2504 Definition....2504 Historical Background....2504 Foundations....2504 Disk Scheduling....2505 Stream Scheduling....2506 Key Applications....2507 Cross-References....2507 Recommended Reading....2507 Multimedia Retrieval Evaluation....2508 Definition....2508 Historical Background....2508 Foundations....2509 Key Applications....2510 Data Sets....2510 Cross-References....2511 Recommended Reading....2511 Multimedia Tagging....2511 Synonyms....2511 Definition....2511 Historical Background....2512 Scientific Fundamentals....2513 Key Applications....2514 Cross-References....2514 Recommended Reading....2514 Multimodal Interfaces....2514 Definition....2514 Historical Background....2515 Foundations....2515 Key Applications....2517 Interaction in Mobile Environments....2518 Geographic Information Systems....2518 Interaction in Adverse Settings....2518 Multimodal Biometric Databases....2518 Interaction in Impairment Conditions....2519 Future Directions....2519 Cross-References....2519 Recommended Reading....2519 Multi-pathing....2520 Definition....2520 Key Points....2520 Cross-References....2520 Multiple Representation Modeling....2520 Synonyms....2520 Definition....2520 Historical Background....2521 Foundations....2522 Multiscale Databases....2522 Multi-Representation Databases....2522 Database Models for Multiple Representations....2522 Architectures for Distributed Representations....2524 Key Applications....2524 Cartography....2524 Multi-Scale Analysis....2525 Future Directions....2525 Cross-References....2525 Recommended Reading....2525 Multi-query Optimization....2526 Synonyms....2526 Definition....2526 Historical Background....2526 Foundations....2527 Challenges....2527 Identifying CSEs....2527 Finding the Optimal Plan in Presence of CSEs....2528 Engineering an Efficient Multi-query Optimizer....2528 Key Applications....2529 Cross-References....2530 Recommended Reading....2530 Multi-resolution Terrain Modeling....2530 Synonyms....2530 Definition....2530 Historical Background....2531 Scientific Fundamentals....2531 Key Applications....2535 Cross-References....2535 Recommended Reading....2535 Multi step Query Processing....2536 Synonyms....2536 Definition....2536 Historical Background....2536 Foundations....2537 General Schema of Multi-step Query Processing....2537 Example: Multi-step Query Processing of Similarity Queries....2538 Example: Algorithms for Multi-step Query Processing of Similarity Queries....2539 Key Applications....2540 Cross-References....2541 Recommended Reading....2541 Multitenancy....2541 Synonyms....2541 Definition....2541 Historical Background....2541 Scientific Fundamentals....2542 Key Applications....2544 Cross-References....2544 Recommended Reading....2544 Multitier Architecture....2544 Synonyms....2544 Definition....2544 Historical Background....2545 Foundations....2545 Key Applications....2546 Cross-References....2547 Recommended Reading....2547 Multitier Storage Systems....2547 Synonyms....2547 Definition....2547 Key Points....2547 Cross-References....2548 Recommended Readings....2548 Multivalued Dependency....2548 Synonyms....2548 Definition....2548 Key Points....2549 Cross-References....2549 Recommended Reading....2549 Multivariate Visualization Methods....2549 Synonyms....2549 Definition....2550 Historical Background....2550 Foundations....2550 Multivariate Continuous Data....2550 Multivariate Categorical Data....2552 Interactive Graphics and Multivariate Graphics....2553 Key Applications....2554 Future Directions....2554 Cross-References....2554 Recommended Reading....2554 Multiversion Serializability and Concurrency Control....2555 Synonyms....2555 Definition....2555 Historical Background....2555 Foundations....2555 Key Applications....2556 Future Directions....2557 Cross-References....2557 Recommended Reading....2557 N....2559 Naive Tables....2559 Synonyms....2559 Definition....2559 Key Points....2559 Cross-References....2560 Recommended Reading....2560 Narrowed Extended XPath I....2560 Synonyms....2560 Definition....2560 Historical Background....2561 Foundations....2561 Requirements....2561 Content Only (CO) Queries....2562 Content and Structure (CAS) Queries....2563 Key Applications....2564 Future Directions....2564 Experimental Results....2564 Data Sets....2564 URL to Code....2564 Cross-References....2565 Recommended Reading....2565 Natural Interaction....2565 Synonyms....2565 Definition....2565 Historical Background....2566 Foundations....2566 Sensing....2567 Intelligence and Presentation....2567 Handling Complexity with TUIs....2568 Key Applications....2569 Multimedia Browsing....2569 Knowledge Exploration and Building....2569 Interactive Museum and Cultural Exhibits....2569 Interactive Music Systems....2570 Cross-References....2570 Recommended Reading....2570 Near-Duplicate Retrieval....2570 Synonyms....2570 Definition....2570 Main Text....2571 Cross-References....2572 Recommended Reading....2572 Nearest Neighbor Classification....2572 Synonyms....2572 Definition....2572 Historical Background....2573 Foundations....2574 Classification Model....2574 Lazy Evaluation Model....2576 Key Applications....2577 Cross-References....2578 Recommended Reading....2578 Nearest Neighbor Query....2578 Synonyms....2578 Definition....2578 Key Points....2578 Cross-References....2579 Recommended Reading....2579 Nearest Neighbor Query in Spatiotemporal Databases....2579 Synonyms....2579 Definition....2579 Historical Background....2579 Foundations....2581 Key Applications....2583 Geographic Information Systems....2583 Location-Based Services....2583 Multi-criteria Decision Making....2583 Future Directions....2583 Experimental Results....2584 Datasets....2584 URL to Code....2584 Cross-References....2584 Recommended Reading....2584 Nested Loop Join....2585 Synonyms....2585 Definition....2585 Key Points....2585 Block Nested Loop Join....2585 Cross-References....2585 Recommended Reading....2585 Nested Transaction Models....2585 Definition....2585 Historical Background....2586 Foundations....2586 Structure of a Nested Transaction....2586 Synchronization of Nested Transactions....2586 Commit/Abort of Nested Transactions....2587 Advantages of Nested Transactions....2587 Key Applications....2588 Cross-References....2588 Recommended Reading....2588 Network Attached Secure Device....2589 Synonyms....2589 Definition....2589 Key Points....2589 Cross-References....2590 Recommended Reading....2590 Network Attached Storage....2590 Synonyms....2590 Definition....2590 Key Points....2590 Cross-References....2590 Recommended Reading....2590 Network Data Model....2590 Synonyms....2590 Definition....2591 Historical Background....2591 Foundations....2591 The Languages....2592 Gross Architecture of a CODASYL DBMS....2592 The Data Structures....2592 Records and Record Types....2592 Record Fields....2593 Sets and Set Types....2593 Areas....2593 Schema and Sub-schemas....2593 Data Manipulation....2594 Data Retrieval....2594 Data Update....2595 Entity-Relationship to Network Mapping....2595 Discussion....2596 Key Applications....2596 Cross-References....2596 Recommended Reading....2596 Neural Networks....2597 Synonyms....2597 Definition....2597 Historical Background....2597 Foundations....2598 Key Applications....2600 Future Directions....2600 Experimental Results....2600 Data Sets....2600 Url to Code....2600 Cross-References....2600 Recommended Reading....2600 N-Gram Models....2601 Definition....2601 Key Points....2601 Cross-References....2602 Recommended Reading....2602 Noise Addition....2602 Synonyms....2602 Definition....2602 Key Points....2602 Cross-References....2602 Recommended Reading....2603 Nonparametric Data Reduction Techniques....2603 Definition....2603 Key Points....2603 Cross-References....2603 Recommended Reading....2603 Nonperturbative Masking Methods....2603 Synonyms....2603 Definition....2604 Key Points....2604 Cross-References....2604 Recommended Reading....2604 Nonrelational Streams....2605 Definition....2605 Main Text....2605 Graph Streams....2605 Spatial Streams....2605 Text Streams....2605 XML Streams....2605 Cross-References....2605 Nonsequenced Semantics....2606 Synonyms....2606 Definition....2606 Key Points....2606 Cross-References....2607 Recommended Reading....2607 Normal Form ORA-SS Schema Diagrams....2607 Synonyms....2607 Definition....2608 Key Points....2608 Cross-References....2609 Recommended Reading....2609 Normal Forms and Normalization....2609 Definition....2609 Historical Background....2610 Foundations....2610 Key Applications....2613 Cross-References....2613 Recommended Reading....2613 NoSQL Stores....2613 Definition....2613 Historical Background....2614 Foundations....2615 Key Applications....2616 URL to Code....2616 Cross-References....2616 Recommended Reading....2617 Now in Temporal Databases....2617 Synonyms....2617 Definition....2617 Historical Background....2617 Foundations....2618 SQL Nullary Functions....2618 Now in End or Stop Columns....2619 Now-Relative Values....2619 Key Applications....2621 Future Directions....2621 Cross-References....2621 Recommended Reading....2621 Null Values....2622 Definition....2622 Key Points....2622 Cross-References....2622 Recommended Reading....2622 O....2623 OASIS....2623 Synonyms....2623 Definition....2623 Key Points....2623 Cross-References....2623 Recommended Reading....2624 Object Constraint Language....2624 Synonyms....2624 Definition....2624 Key Points....2624 Cross-References....2625 Recommended Reading....2625 Object Data Models....2625 Synonyms....2625 Definition....2625 Historical Background....2626 Foundations....2626 Characteristics of Object Data Models....2626 Object-Oriented Data Model....2628 Object-Relational Data Model....2630 Key Applications....2632 Cross-References....2632 Recommended Reading....2632 Object Identity....2632 Synonyms....2632 Definition....2633 Key Points....2633 Cross-References....2633 Recommended Reading....2633 Object Recognition....2633 Synonyms....2633 Definition....2633 Historical Background....2633 Foundations....2634 Geometry-Based Approaches....2634 Appearance-Based Algorithms....2634 Feature-Based Algorithms....2635 Key Applications....2635 Future Directions....2635 Data Sets....2636 URL to Code....2636 Cross-References....2636 Recommended Reading....2636 Object Relationship Attribute Data Model for Semistructured Data....2637 Synonyms....2637 Definition....2637 Key Points....2637 Cross-References....2639 Recommended Reading....2639 Object Storage Protocol....2639 Synonyms....2639 Definition....2639 Main Text....2639 Recommended Reading....2640 Object-Role Modeling....2640 Synonyms....2640 Definition....2640 Historical Background....2640 Foundations....2641 Key Applications....2645 Future Directions....2645 Cross-References....2645 Recommended Reading....2645 OLAM....2646 Synonyms....2646 Definition....2646 Historical Background....2646 Scientific Fundamentals....2647 Key Applications....2649 Future Directions....2649 Cross-References....2649 Recommended Reading....2649 OLAP Personalization and Recommendation....2650 Definition....2650 Historical Background....2651 Scientific Fundamentals....2651 Key Applications....2653 Future Directions....2654 Experimental Results....2654 Data Sets....2654 URL to Code....2654 Cross-References....2654 Recommended Readings....2654 One-Copy-Serializability....2655 Synonyms....2655 Definition....2655 Main Text....2655 Cross-References....2656 Recommended Readings....2656 One-Pass Algorithm....2656 Synonyms....2656 Definition....2656 Key Points....2657 Cross-References....2657 Recommended Reading....2657 Online Analytical Processing....2658 Synonyms....2658 Definition....2658 Historical Background....2658 Foundations....2659 Operations....2660 Declarative Languages....2661 Key Applications....2662 Future Directions....2662 Url to Code....2662 Cross-References....2663 Recommended Reading....2663 Online Recovery in Parallel Database Systems....2664 Synonyms....2664 Definition....2664 Historical Background....2664 Foundations....2666 Key Applications....2669 Cross-References....2669 Recommended Reading....2669 Ontologies and Life Science Data Management....2670 Synonyms....2670 Definition....2670 Historical Background....2670 Foundations....2671 Key Applications....2672 Future Directions....2672 Cross-References....2673 Recommended Reading....2673 Ontology....2674 Synonyms....2674 Definition....2674 Historical Background....2674 Foundations....2675 Key Applications....2676 Recommended Reading....2676 Ontology Elicitation....2676 Synonyms....2676 Definition....2677 Historical Background....2677 Conceptual Modeling....2677 Data Schema Versus Ontology....2677 Foundations....2678 Lexical Versus Semantic Level....2678 Lexical Variability and Reusability....2679 Semantic Versus Pragmatic Level....2680 Divergence and Conflict....2681 Convergence and Patterns....2681 Key Applications....2681 Semantic Web Services....2681 Regulatory Compliance....2681 Human Resources....2682 Future Directions....2682 Cross-References....2683 Recommended Reading....2683 Ontology Engineering....2684 Synonyms....2684 Definition....2684 Ontology Engineering: Details....2684 Cross-References....2685 Recommended Reading....2685 Ontology Visual Querying....2685 Definition....2685 Historical Background....2685 Foundations....2686 Key Applications....2688 Future Directions....2689 Cross-References....2689 Recommended Reading....2689 Ontology-Based Data Access and Integration....2690 Definition....2690 Historical Background....2690 Scientific Fundamentals....2691 OBDA Framework....2691 A Tractable OBDA Framework....2692 Techniques for Query Answering via Rewriting....2693 Query Rewriting w.r.t. the Ontology....2694 Query Rewriting w.r.t. the Mapping....2694 Key Applications....2695 Future Directions....2695 Cross-References....2696 Recommended Reading....2696 Open Database Connectivity....2696 Synonyms....2696 Definition....2696 Key Points....2697 Cross-References....2697 Recommended Reading....2697 Open Nested Transaction Models....2697 Synonyms....2697 Definition....2697 Historical Background....2697 Foundations....2698 Key Applications....2699 Future Directions....2700 Cross-References....2700 Recommended Reading....2700 Operator-Level Parallelism....2701 Synonyms....2701 Definition....2701 Historical Background....2701 Foundations....2701 Classes of Parallelism....2702 Effect of Query Plan Selection on Operator-Level Parallelism....2702 Other Factors Limiting Operator-Level Parallelism....2704 Relation to Inter-query and Intra-operator Parallelism....2705 Key Applications....2705 Cross-References....2705 Recommended Reading....2705 Opinion Mining....2706 Synonyms....2706 Definition....2706 Historical Background....2706 Foundations....2707 Model of Opinion Mining....2707 Sentiment Classification....2709 Feature-Based Opinion Mining....2710 Mining Comparative and Superlative Sentences....2710 Key Applications....2711 Cross-References....2711 Recommended Reading....2711 Optimistic Replication and Resolution....2712 Synonyms....2712 Definition....2712 Historical Background....2712 Foundations....2713 Transmitting and Replaying Updates....2714 Conflicts....2714 Conflict Resolution and Reconciliation....2715 Last Writer Wins....2715 Semantic Resolvers....2715 Operational Transformation....2716 Conflict-Free Replicated Data Types (CRDTs)....2716 Scheduling Transactions Content and Ordering....2716 Freshness of Replicas....2717 Optimistic Replication Versus Optimistic Concurrency Control....2717 Key Applications....2717 Cross-References....2718 Recommended Reading....2718 Optimization and Tuning in Data Warehouses....2719 Synonyms....2719 Definition....2719 Historical Background....2720 Scientific Fundamentals....2720 Redundant Techniques....2720 Nonredundant Techniques....2724 Tuning....2726 Key Applications....2726 Future Directions....2726 Experimental Results....2727 Data Sets....2727 Cross-References....2727 Recommended Reading....2727 OQL....2729 Synonyms....2729 Definition....2729 Key Points....2729 Cross-References....2730 Recommended Reading....2730 Orchestration....2730 Definition....2730 Key Points....2730 Cross-References....2731 Recommended Reading....2731 Order Dependency....2731 Synonyms....2731 Definition....2731 Historical Background....2731 Scientific Fundamentals....2732 Key Applications....2732 Recommended Readings....2732 OR-Join....2732 Synonyms....2732 Definition....2732 Key Points....2733 Cross-References....2733 OR-Split....2733 Synonyms....2733 Definition....2733 Key Points....2733 Cross-References....2733 OSQL....2734 Definition....2734 Key Points....2734 Cross-References....2734 Recommended Reading....2734 Outlier Detection....2735 Synonyms....2735 Definition....2735 Historical Background....2735 Scientific Fundamentals....2735 Database-Oriented Efficient Outlier Models....2735 Distance-Based Outlier Detection....2735 Local Outlier Factor....2736 Categories and Variants....2737 Global and Local Outlier Detection....2737 Distance-Based and Density-Based....2737 Variants for Improved Efficiency....2737 Application-Specific Methods and Generalized Models....2737 Recent Developments....2737 Key Applications....2738 Future Directions....2738 URL to Code....2738 Cross-References....2739 Recommended Reading....2739 Overlay Network....2739 Definition....2739 Key Points....2739 Cross-References....2740 OWL: Web Ontology Language....2740 Synonyms....2740 Definition....2740 Key Points....2741 Cross-References....2741 Recommended Reading....2741 P....2742 P/FDM....2742 Definition....2742 Key Points....2742 Cross-References....2743 Recommended Reading....2743 Parallel and Distributed Data Warehouses....2743 Synonyms....2743 Definition....2743 Historical Background....2744 Scientific Fundamentals....2745 Future Directions....2752 Experimental Results....2752 Cross-References....2752 Recommended Reading....2752 Parallel Coordinates....2753 Synonyms....2753 Definition....2753 Historical Background....2754 Foundations....2755 Key Applications....2758 Future Directions....2759 Cross-References....2759 Recommended Reading....2759 A. Inselberg, Visual Multidimensional Geometry and its Applications, 550 pages, Springer, 2009....2759 Parallel Data Placement....2760 Synonyms....2760 Definition....2760 Historical Background....2760 Foundations....2760 Key Applications....2762 Recommended Reading....2762 Parallel Database Management....2762 Synonyms....2762 Definition....2762 Historical Background....2763 Foundations....2763 Key Applications....2765 Recommended Reading....2765 Parallel Hash Join, Parallel Merge Join, Parallel Nested Loops Join....2765 Synonyms....2765 Definition....2765 Key Points....2766 Cross-References....2767 Recommended Reading....2767 Parallel Query Execution Algorithms....2767 Synonyms....2767 Definition....2767 Historical Background....2767 Foundations....2767 Pipelining....2768 Partitioning....2768 Bushy Execution....2769 Specifics of Parallel Algorithms....2769 Parallel Execution Beyond Queries....2771 Key Applications....2772 Future Directions....2772 Cross-References....2773 Recommended Reading....2773 Parallel Query Optimization....2773 Synonyms....2773 Definition....2773 Historical Background....2773 Foundations....2773 Extending Query Plans to Execute in Parallel on Partitioned Data....2774 Extending the Search Algorithm to Include Parallel Plans....2774 Costing Parallel Query Plans....2775 Heuristics to Reduce the Number of Parallel Plans Considered....2775 Key Applications....2775 Future Directions....2775 Cross-References....2775 Recommended Reading....2775 Parallel Query Processing....2776 Synonyms....2776 Definition....2776 Historical Background....2777 Foundations....2777 Key Applications....2778 Cross-References....2779 Recommended Reading....2779 Parameterized Complexity of Queries....2779 Definition....2779 Historical Background....2779 Foundations....2779 Fixed-Parameter Tractability....2779 Set Cover....2780 Fixed-Parameter Intractability....2780 Parameterized Query Evaluation....2781 Further Positive Results on Query Evaluation Complexity....2781 Key Applications....2782 References....2782 Parametric Data Reduction Techniques....2783 Definition....2783 Key Points....2783 Cross-References....2784 Recommended Reading....2784 Partial Replication....2784 Definition....2784 Main Text....2784 Scalability....2784 Fast Local Access....2785 Fault-Tolerance and Available....2785 Challenges....2785 Cross-References....2786 Recommended Reading....2786 Path Query....2786 Synonyms....2786 Definition....2786 Historical Background....2786 Foundations....2787 Path Query and Pattern Tree Matching....2788 Path Query Languages....2788 Path Query Evaluation....2789 Path Query Optimization....2789 Indices for Path Query Evaluation....2789 Key Applications....2790 Future Directions....2790 Data Sets....2790 Cross-References....2791 Recommended Reading....2791 Pattern-Growth Methods....2791 Definition....2791 Historical Background....2791 Foundations....2792 Frequent Itemset Mining....2792 Sequential Pattern Mining....2792 Frequent Subgraph Mining....2793 Key Applications....2794 Future Directions....2794 Mining Approximate or Noise-Tolerant Patterns....2794 Pattern-Based Classification and Clustering....2794 Experimental Results....2794 Data Sets....2794 Synthetic Data....2794 Real Data....2795 URL to Code....2795 Cross-References....2795 Recommended Reading....2795 Peer Data Management System....2795 Synonyms....2795 Definition....2796 Key Points....2796 Cross-References....2797 Recommended Reading....2797 Peer-to-Peer Content Distribution....2797 Synonyms....2797 Definition....2797 Historical Background....2797 Foundations....2798 File Distribution....2798 Video Streaming....2799 Performance Analysis of Distribution Architectures....2799 Key Applications....2801 Future Directions....2801 Cross-References....2801 Recommended Reading....2801 Peer-to-Peer Data Integration....2802 Definition....2802 Historical Background....2802 Foundations....2804 Key Applications....2806 Cross-References....2806 Recommended Reading....2806 Peer-to-Peer Overlay Networks: Structure, Routing and Maintenance....2806 Definition....2806 Historical Background....2807 Foundations....2807 Taxonomy....2807 Purpose of Use....2807 Overlay Structure....2808 Centralized Overlays....2808 Decentralized Overlays....2808 Hybrid Overlays....2809 Routing....2809 Routing in Unstructured Overlays....2809 Routing in Structured Overlays....2810 Maintenance....2811 Key Applications....2811 Cross-References....2812 Recommended Reading....2812 Peer-to-Peer Publish-Subscribe Systems....2812 Definition....2812 Historical Background....2813 Foundations....2813 Key Applications....2816 Experimental Results....2817 Data Sets....2817 Cross-References....2817 Recommended Reading....2818 Peer-to-Peer Storage....2818 Synonyms....2818 Definition....2818 Historical Background....2819 Foundations....2820 Resilience from Redundancy....2821 Maintaining Redundancy....2822 Placement Strategies....2823 Analysis Techniques....2824 Key Applications....2825 Cross-References....2825 Recommended Reading....2825 Peer-to-Peer System....2826 Synonyms....2826 Definition....2826 Key Points....2826 Cross-References....2827 Recommended Reading....2827 Peer-to-Peer Web Search....2827 Definition....2827 Historical Background....2827 Foundations....2828 P2P Global Computing for Scalable Search-Engine Functionality....2828 P2P Social Computing with Autonomous Peers....2828 Query Routing....2829 Search Result Ranking....2829 Key Applications....2830 Future Directions....2830 Cross-References....2830 Recommended Reading....2830 Performance Analysis of Transaction Processing Systems....2831 Synonyms....2831 Definition....2831 Historical Background....2831 Foundations....2832 Queueing Network Models: QNMs....2832 Buffer Miss Rate (BMR)....2834 Performance Analysis of Storage Systems....2834 Performance Analysis of Concurrency Control Methods....2835 Standard Locking....2835 Restart-Oriented Locking Methods....2837 Optimistic Concurrency Control....2838 Conclusion....2839 Cross-References....2839 Recommended Reading....2839 Performance Monitoring Tools....2840 Definition....2840 Historical Background....2840 Foundations....2840 Event Monitor....2840 Query Plan Explainer....2840 Profiler....2840 Key Applications....2841 Cross-References....2841 Recommended Reading....2841 Period-Stamped Temporal Models....2841 Synonyms....2841 Definition....2841 Historical Background....2841 Scientific Fundamentals....2842 Examples Illustrating Inadequacy of Conventional Models to Support Time Period....2842 Common Characteristics of Period-Stamped Data Models....2843 Desired Behavior of Period-Stamped Data Models....2843 Literature Overview....2844 Key Applications....2846 Future Directions....2846 Cross-References....2846 Recommended Reading....2846 Personalized Web Search....2847 Synonyms....2847 Definition....2847 Historical Background....2847 Foundations....2847 User Profiling....2847 Personalized Search Based on Content Analysis....2848 Personalized Web Search Based on Hyperlink Analysis....2849 Community-Based Personalized Web Search....2850 Server-Side and Client-Side Implement....2850 Challenges of Personalized Search....2851 Key Applications....2851 Experimental Results....2851 Cross-References....2851 Recommended Reading....2852 Petri Nets....2852 Synonyms....2852 Definition....2852 Historical Background....2853 Foundations....2853 Key Applications....2856 Workflow Management and BPM....2856 Discrete/Flexible Manufacturing....2857 Communication Protocols....2857 Embedded Systems....2857 Cross-References....2857 Recommended Reading....2857 Physical Clock....2857 Synonyms....2857 Definition....2857 Key Points....2857 Cross-References....2858 Recommended Reading....2858 Physical Database Design for Relational Databases....2858 Synonyms....2858 Definition....2858 Historical Background....2859 Foundations....2859 Infrastructure Mechanics....2859 Design Choices....2860 Combining Physical Design Choices....2860 Other Physical Database Design Techniques....2860 Key Applications....2862 Lifecycle Differences....2862 Application Domains....2862 Future Directions....2863 Cross-References....2863 Recommended Reading....2863 Physical Layer Tuning....2864 Definition....2864 Historical Background....2864 Foundations....2864 Hardware Tuning....2864 Operating System Tuning....2865 Key Applications....2865 Cross-References....2865 Recommended Reading....2865 Pipeline....2866 Definition....2866 Key Points....2866 Pipelining....2867 Definition....2867 Key Points....2867 Cross-References....2867 Recommended Reading....2867 Platform-as-a-Service (PaaS)....2868 Synonyms....2868 Definition....2868 Overview....2868 Cross-References....2868 References....2868 Point-in-Time Copy....2868 Synonyms....2868 Definition....2869 Key Points....2869 Cross-References....2869 Recommended Reading....2869 Point-Stamped Temporal Models....2869 Synonyms....2869 Definition....2869 Historical Background....2869 Foundations....2870 Timestamps and Database Objects....2870 The Snapshot Model....2870 The Timestamp Model....2870 The Parametric Model....2871 Multiple Atomic Timestamps....2871 Models with a Fixed Number of Timestamp Attributes....2871 Models with a Varying Number of Timestamp Attributes....2872 Sets of Timestamps: Compact Representation....2872 Query Languages and Integrity Constraints....2873 Key Applications....2873 Cross-References....2873 Recommended Reading....2874 Polytransactions....2874 Definition....2874 Key Points....2874 Cross-References....2875 Recommended Reading....2875 Positive Relational Algebra....2875 Synonyms....2875 Definition....2875 Key Points....2876 Cross-References....2876 Recommended Reading....2876 Possible Answers....2876 Synonyms....2876 Definition....2876 Key Points....2876 Cross-References....2877 Recommended Reading....2877 PRAM....2877 Synonyms....2877 Definition....2877 Key Points....2877 Cross-References....2877 Recommended Reading....2877 Precision....2877 Definition....2877 Key Points....2878 Cross-References....2878 Precision and Recall....2878 Synonyms....2878 Definition....2878 Key Points....2878 Cross-References....2878 Recommended Reading....2878 Precision at n....2879 Synonyms....2879 Definition....2879 Key Points....2879 Cross-References....2879 Precision-Oriented Effectiveness Measures....2879 Definition....2879 Historical Background....2880 Foundations....2880 Key Applications....2881 Data Sets....2881 Cross-References....2881 Recommended Reading....2881 Predictive Analytics....2881 Synonyms....2881 Definition....2882 Main Text....2882 Cross-References....2882 Recommended Readings....2882 Preference Queries....2883 Synonyms....2883 Definition....2883 Historical Background....2883 Scientific Fundamentals....2883 Key Applications....2884 Future Directions....2885 Cross-References....2885 Recommended Reading....2885 Preference Specification....2886 Synonyms....2886 Definition....2886 Historical Background....2886 Scientific Fundamentals....2887 Key Applications....2889 Future Directions....2889 Cross-References....2890 Recommended Reading....2890 Prescriptive Analytics....2891 Synonyms....2891 Definition....2891 Main Text....2891 Cross-References....2892 Recommended Reading....2892 Presenting Structured Text Retrieval Results....2892 Synonyms....2892 Definition....2892 Historical Background....2892 Foundations....2893 Key Applications....2896 Future Directions....2896 Data Sets....2896 Cross-References....2897 Recommended Reading....2897 Primary Index....2897 Synonyms....2897 Definition....2898 Key Points....2898 Cross-References....2898 Recommended Reading....2898 Principal Component Analysis....2899 Synonyms....2899 Definition....2899 Key Points....2899 Cross-References....2899 Recommended Reading....2899 Privacy....2899 Definition....2899 Key Points....2900 Cross-References....2900 Recommended Reading....2900 Privacy Metrics....2900 Synonyms....2900 Definition....2900 Historical Background....2901 Foundations....2901 Key Applications....2902 Future Directions....2903 Cross-References....2903 Recommended Reading....2903 Privacy Policies and Preferences....2903 Definition....2903 Historical Background....2903 Foundations....2904 Key Applications....2905 Cross-References....2906 Recommended Reading....2906 Privacy Through Accountability....2906 Definition....2906 Historical Background....2907 Scientific Fundamentals....2907 Checking Audit Logs for Temporal Restrictions on Direct Flows....2907 Checking Audit Logs for Purpose Restrictions on Direct and Implicit Flows....2909 Checking Black-Box Software Systems for Statistical Privacy Properties....2909 Checking Source Code of Software Systems for Privacy Properties....2910 Key Applications....2910 Recommended Reading....2910 Privacy-Enhancing Technologies....2911 Synonyms....2911 Definition....2911 Historical Background....2912 Scientific Fundamentals....2912 PETs for Minimizing or Avoiding Personally Identifiable Data....2912 Data Minimization at Communication Level....2912 Data Minimization at Application Level....2914 PETs for Safeguarding Lawful and Privacy-Friendly Personal Data Processing....2916 PETs that Are a Combination of the Two Aforementioned PET Classes....2917 Key Applications....2917 Cross-References....2917 Recommended Reading....2917 Privacy-Preserving Data Mining....2918 Definition....2918 Historical Background....2918 Foundations....2918 Key Applications....2919 Future Directions....2920 Cross-References....2920 Recommended Reading....2920 Privacy-Preserving DBMSs....2921 Introduction....2921 Privacy Fundamentals....2921 Fundamentals of a PP-DBMS....2921 Future Directions....2922 Recommended Reading....2923 Private Information Retrieval....2924 Definition....2924 Historical Background....2924 Foundations....2925 Key Applications....2926 Future Directions....2928 Cross-References....2928 Recommended Reading....2928 Probabilistic Databases....2929 Synonyms....2929 Definition....2930 Historical Background....2930 Scientific Fundamentals....2930 Probabilistic Databases and Markov Logic Networks....2934 Key Applications....2934 Cross-References....2935 Recommended Reading....2935 Probabilistic Entity Resolution....2936 Synonyms....2936 Definition....2936 Historical Background....2936 Scientific Fundamentals....2937 Exclusive Instance Alternatives....2937 Probabilistic Schema Mappings....2937 Querying Probabilistic Matches....2937 Key Applications....2938 Cross-References....2938 Recommended Reading....2938 Probabilistic Retrieval Models and Binary Independence Retrieval (BIR) Model....2938 Synonyms....2938 Definition....2938 Historical Background....2939 Foundations....2939 Derivation of the BIR Model....2939 Bayes Theorem....2939 Binary Feature Vector ....2940 Independence Assumption....2940 Product Split....2940 Non-query Term Assumption....2940 Rewriting to Achieve Compact Form....2940 Alternative Derivation....2941 Estimation of Term Probabilities....2941 Variations of the BIR Term Weight....2942 Solving the Zero Probability Problem....2942 Relationship Between the BIR Model, IDF, and BM25....2942 Key Applications....2943 Cross-References....2943 Recommended Reading....2943 Probabilistic Skylines....2944 Synonyms....2944 Definition....2944 Historical Background....2944 Scientific Fundamentals....2944 Future Directions....2945 Key Applications....2945 Cross-References....2946 Recommended Reading....2946 Probabilistic Spatial Queries....2946 Synonyms....2946 Definition....2946 Historical Background....2946 Foundations....2947 Key Applications....2950 Future Directions....2950 URL to Code....2950 Cross-References....2950 Recommended Reading....2950 Probabilistic Temporal Databases....2951 Synonyms....2951 Definition....2951 Historical Background....2951 Foundations....2953 Key Applications....2954 Future Directions....2954 Cross-References....2955 Recommended Reading....2955 Probability Ranking Principle....2955 Synonyms....2955 Definition....2955 Key Points....2956 Cross-References....2956 Recommended Reading....2956 Probability Smoothing....2956 Definition....2956 Key Points....2956 Cross-References....2957 Recommended Reading....2957 Process Life Cycle....2957 Synonyms....2957 Definition....2958 Key Points....2958 Cross-References....2958 Process Mining....2958 Synonyms....2958 Definition....2958 Key Points....2959 Cross-References....2960 Recommended Reading....2960 Process Optimization....2961 Synonyms....2961 Definition....2961 Historical Background....2961 Foundations....2962 Key Applications....2965 Context-Aware Business Process....2965 E-Science and Grid Computing....2965 Future Directions....2965 Experimental Results....2966 Cross-References....2966 Recommended Reading....2966 Process Structure of a DBMS....2966 Synonyms....2966 Definition....2966 Historical Background....2966 Foundations....2968 Layers of the DBMS and Application....2968 Client-Server Computing....2969 Multi-Database Computing....2969 Service-Oriented Architectures (SOA)....2971 Shared-Memory (Single Database) DBMS Architectures....2972 Shared-Disk (Single Database) DBMS Architectures....2972 Shared-Nothing (Single Database) DBMS Architectures....2972 Implications of Shared-Nothing, Shared-Disk, and Shared-Everything Architectures....2973 Key Applications....2975 Cross-References....2975 Recommended Reading....2976 Processing Overlaps in Structured Text Retrieval....2976 Synonyms....2976 Definition....2976 Historical Background....2976 Foundations....2977 Using Element Types....2978 Using Paths....2978 Using Structural Relationships for Re-Ranking....2979 Key Applications....2980 Experimental Results....2980 Data Sets....2981 Cross-References....2981 Recommended Reading....2981 Processing Structural Constraints....2981 Definition....2981 Historical Background....2981 Foundations....2982 User Querying Behavior....2982 Structural Constraints....2982 Processing Structural Constraints....2983 Ignoring Structural Constraints....2983 Tag Equivalence....2983 Structure Boosting....2984 Score Propagation....2984 Key Applications....2984 Future Directions....2984 Experimental Results....2985 Cross-References....2985 Recommended Reading....2985 Processor Cache....2986 Synonyms....2986 Definition....2986 Key Points....2986 Cross-References....2987 Profiles and Context for Structured Text Retrieval....2987 Definition....2987 Historical Background....2988 Scientific Fundamentals....2988 Key Applications....2990 Experimental Results....2991 Data Sets....2991 Recommended Reading....2991 Projection....2992 Synonyms....2992 Definition....2992 Key Points....2992 Cross-References....2992 Propagation-Based Structured Text Retrieval....2993 Synonyms....2993 Definition....2993 Historical Background....2993 Foundations....2994 Indexing....2994 Relevance Score Evaluation for Content-Only Queries....2995 Scoring Leaf Elements....2995 Propagating Relevance Scores....2995 Content-and-Structure Query Processing....2997 Key Applications....2997 Experimental Results....2997 Data Sets....2997 Cross-References....2997 Recommended Reading....2998 Protection from Insider Threats....2998 Synonyms....2998 Definition....2998 References....2999 Provenance and Reproducibility....2999 Synonyms....2999 Definition....2999 Historical Background....2999 Scientific Fundamentals....3000 Key Applications....3001 URL to Code....3002 Cross-References....3003 Recommended Reading....3003 Provenance in Databases....3003 Synonyms....3003 Definition....3003 Historical Background....3004 Scientific Fundamentals....3004 Key Applications....3005 URL to Code....3005 Cross-References....3005 Recommended Reading....3006 Provenance in Scientific Databases....3006 Synonyms....3006 Definition....3006 Historical Background....3007 Foundations....3007 Key Applications....3010 URL to Code....3010 Cross-References....3010 Recommended Reading....3010 Provenance in Workflows....3011 Synonyms....3011 Definition....3011 Historical Background....3012 Scientific Fundamentals....3012 Key Applications....3013 URL to Code....3014 Cross-References....3015 Recommended Reading....3015 Provenance Standards....3015 Synonyms....3015 Definition....3015 Historical Background....3016 Scientific Fundamentals....3017 Entities, Activities, and Agents....3017 Core Provenance Relationships....3019 Constraints and Inferences....3019 Actors and Their Relationships....3021 PROV-O....3021 Extensibility....3021 Further Reading....3021 Key Applications....3021 Future Directions....3021 URL to CODE....3021 Cross-References....3022 Recommended Reading....3022 Provenance Storage....3022 Synonyms....3022 Definition....3022 Historical Background....3023 Scientific Fundamentals....3023 Key Applications....3024 Cross-References....3024 Recommended Reading....3024 Provenance: Privacy and Security....3026 Synonyms....3026 Definition....3026 Historical Background....3026 Scientific Fundamentals....3027 Desiderata of Provenance Privacy and Security....3028 Provenance Privacy....3028 Provenance Security....3029 Mechanisms for Provenance Privacy and Security....3029 Key Applications....3029 Future Directions *....3030 Cross-References....3030 Recommended Reading*....3031 Pseudonymity....3031 Synonyms....3031 Definition....3031 Key Points....3031 Cross-References....3032 Recommended Reading....3032 Publish/Subscribe....3032 Definition....3032 Historical Background....3032 Foundations....3034 Key Applications....3035 Data Sets....3036 Cross-References....3036 Recommended Reading....3036 Publish/Subscribe Over Streams....3036 Definition....3036 Historical Background....3037 Foundations....3038 Centralized, Stateless Publish/Subscribe....3039 Centralized, Stateful Publish/Subscribe....3039 Distributed, Stateless Publish/Subscribe....3040 Distributed, Stateful Publish/Subscribe....3040 Key Applications....3041 Data Sets....3041 Cross-References....3041 Recommended Reading....3041 Punctuations....3042 Definition....3042 Key Points....3042 Cross-References....3043 Recommended Reading....3043 Q....3044 Q-Measure....3044 Synonyms....3044 Definition....3044 Main Text....3044 Cross-References....3045 Quadtrees (and Family)....3045 Synonyms....3045 Definition....3045 Historical Background....3045 Foundations....3046 Point Quadtree....3046 Region Quadtree....3047 PR Quadtree....3048 PMR Quadtree....3049 XBR Tree....3049 Quadtree and Time-Evolving Regional Data....3050 Key Applications....3050 Future Directions....3051 Cross-References....3051 Recommended Reading....3051 Qualitative Temporal Reasoning....3052 Synonyms....3052 Definition....3052 Historical Background....3052 Scientific Fundamentals....3053 Key Applications....3055 Future Directions....3055 Cross-References....3056 Recommended Reading....3056 Quality and Trust of Information Content and Credentialing....3056 Definition....3056 Key Points....3056 Cross-References....3057 Recommended Reading....3057 Quality of Data Warehouses....3057 Definition....3057 Historical Background....3058 Foundations....3058 Quality of DBMS....3058 Quality of Data Warehouse Data Models....3059 Data Quality....3061 Key Applications....3063 Future Directions....3063 Experimental Results....3063 Cross-References....3063 Recommended Reading....3063 Quantiles on Streams....3064 Synonyms....3064 Definition....3064 Historical Background....3064 Foundations....3065 Randomized Algorithms....3066 Deterministic Algorithms....3066 Practical Considerations....3067 Extensions....3067 Quantiles in Distributed Streams....3067 Quantiles in Sliding Windows....3067 Biased Estimate of Quantiles....3067 Duplicate Insensitive Quantiles....3068 Key Applications....3068 Future Directions....3068 Cross-References....3068 Recommended Reading....3068 Quantitative Association Rules....3069 Synonyms....3069 Definition....3069 Historical Background....3070 Foundations....3071 Frequent Rules....3071 Distributional Rules....3072 Structure Patterns....3073 Key Applications....3074 Future Directions....3074 Cross-References....3074 Recommended Reading....3074 QUEL....3074 Definition....3074 Key Points....3075 Query by Humming....3075 Synonyms....3075 Definition....3075 Historical Background....3075 Foundations....3075 Comparisons of Distance Measures on Examples....3075 Dynamic Time Warping (DTW)....3076 Constraints and Lower Bounds on Dynamic Time Warping....3077 Uniform Scaling (US)....3077 Lower Bounding Uniform Scaling....3077 Scaling and Time Warping (SWM)....3078 Lower Bounding SWM....3078 Efficient Pruning Algorithm by Lower Bounds....3079 Key Applications....3079 Future Directions....3079 Experimental Results....3079 Data Sets....3080 Cross-References....3080 Recommended Reading....3080 Query Containment....3080 Definition....3080 Historical Background....3080 Scientific Fundamentals....3081 Key Applications....3082 Cross-References....3084 Recommended Reading....3084 Query Evaluation Techniques for Multidimensional Data....3085 Synonyms....3085 Definition....3085 Key Points....3085 Cross-References....3085 Recommended Reading....3085 Query Expansion for Information Retrieval....3085 Synonyms....3085 Definition....3085 Historical Background....3086 Foundations....3086 Query Expansion Following Relevance and Pseudo-relevance Feedback....3087 Query Expansion Using Association Thesauri and Term Co-occurrence Measures....3088 Interactive Query Expansion....3089 Key Applications....3089 Cross-References....3089 Recommended Reading....3089 Query Expansion Models....3090 Synonyms....3090 Definition....3090 Historical Background....3090 Foundations....3090 Key Applications....3092 Experimental Results....3092 Cross-References....3093 Recommended Reading....3093 Query Language....3093 Synonyms....3093 Definition....3093 Key Points....3094 Cross-References....3094 Query Languages and Evaluation Techniques for Biological Sequence Data....3094 Synonyms....3094 Definition....3094 Historical Background....3095 Foundations....3095 Index Structures....3096 Key Applications....3097 Cross-References....3097 Recommended Reading....3097 Query Languages for the Life Sciences....3098 Synonyms....3098 Definition....3098 Historical Background....3098 Foundations....3099 Key Applications....3100 Future Directions....3101 Data Sets....3102 URL to Code....3102 Cross-References....3102 Recommended Reading....3102 Query Load Balancing in Parallel Database Systems....3103 Synonyms....3103 Definition....3103 Historical Background....3103 Foundations....3103 Load-Balancing Problems....3103 Intraoperator Load Balancing....3105 Interoperator Load Balancing....3106 Intra-query Load Balancing....3106 Key Applications....3106 Data Sets....3107 Cross-References....3107 Recommended Reading....3107 Query Optimization....3107 Synonyms....3107 Definition....3107 Key Points....3108 Cross-References....3108 Recommended Reading....3108 Query Optimization (in Relational Databases)....3108 Synonyms....3108 Definition....3108 Historical Background....3109 Foundations....3109 Optimizing Simple Queries....3110 More Complex Queries....3113 Key Applications....3114 Cross-References....3114 Recommended Reading....3114 Query Optimization in Sensor Networks....3114 Synonyms....3114 Definition....3114 Historical Background....3115 Scientific Fundamentals....3115 Queries....3115 Query Plan....3115 Metadata....3115 Cost Model....3116 Centralized Optimization....3116 Distributed Optimization....3117 Complex Event Detection: Join Processing....3117 Key Applications....3118 Future Directions....3118 Cross-References....3118 Recommended Reading....3118 Query Plan....3119 Synonyms....3119 Definition....3119 Key Points....3119 Cross-References....3119 Recommended Reading....3119 Query Point Movement Techniques for Content-Based Image Retrieval....3119 Definition....3119 Historical Background....3120 Foundations....3121 Naïve Random Scan Method (NRS)....3122 Local Neighboring Movement Method (LNM)....3122 Neighboring Divide and Conquer Method (NDC)....3122 Global Divide and Conquer Method (GDC)....3123 Key Applications....3124 Future Directions....3124 Experimental Results....3124 Data Sets....3125 Recommended Reading....3125 Query Processing....3125 Synonyms....3125 Definition....3125 Key Points....3125 Cross-References....3126 Recommended Reading....3126 Query Processing (in Relational Databases)....3126 Synonyms....3126 Definition....3126 Historical Background....3126 Foundations....3128 Key Applications....3131 Recommended Reading....3131 Query Processing and Optimization in Object Relational Databases....3131 Synonyms....3131 Definition....3131 Historical Background....3132 Foundations....3132 The Four Phases of Query Processing....3132 The Fundamentals of a (Physical) Query Optimizer....3133 Formalisms and Approaches for Query Processing and Query Optimization....3134 Implementing Query Optimizers....3134 Key Applications....3134 Future Directions....3134 Experimental Results....3135 Cross-References....3135 Recommended Reading....3135 Query Processing in Data Integration Systems....3135 Synonyms....3135 Definition....3136 Historical Background....3136 Scientific Fundamentals....3136 Optimizing a Data Integration Query....3136 Executing a Data Integration Query....3137 Adaptive Query Processing....3137 Key Applications....3138 Cross-References....3138 Recommended Reading....3138 Query Processing in Data Warehouses....3138 Synonyms....3138 Definition....3139 Historical Background....3139 Foundations....3140 Requirements and Specifics of the Analytical Context....3140 Potential and Solutions for Efficient Data Warehouse Query Processing....3140 Part I: Query Planning and Execution....3141 Optimizing the Optimization Process....3141 Optimization Goal....3141 Specific Rewrite Rules....3141 HW-Assisted Query Execution....3141 Multi-query Optimization....3141 Part II: Considering Logical Access Paths....3141 Partition Management....3141 Materialized Views....3142 Part III: Considering Physical Access Paths....3142 Data Organization....3142 Compression and Main-Memory Techniques....3142 Additional Index Structures....3142 Multidimensional Clustering Schemes....3142 Part IV: Alternative Query Answering Models....3143 Online Aggregation....3143 Approximate Query Answering/Approximate Query Processing....3143 Key Applications....3143 Future Directions....3143 Cross-References....3144 Recommended Reading....3144 Query Processing in Deductive Databases....3145 Synonyms....3145 Definition....3145 Historical Background....3145 Foundations....3145 Evaluation of Datalog Programs....3146 Optimization of Datalog Programs....3148 Negation in Datalog....3149 Key Applications....3150 Cross-References....3151 Recommended Reading....3151 Query Processing over Uncertain Data....3151 Synonyms....3151 Definition....3151 Scientific Fundamentals....3151 Representation of Uncertain Data....3151 Complexity of Query Processing....3152 Query Processing Techniques....3152 In-Database Techniques....3153 Out-Database Techniques....3154 Historical Background....3155 Key Applications....3155 Cross-References....3156 Recommended Reading....3156 Query Processor....3157 Synonyms....3157 Definition....3157 Key Points....3157 Cross-References....3158 Recommended Reading....3158 Query Rewriting....3159 Synonyms....3159 Definition....3159 Key Points....3159 Cross-References....3159 Recommended Reading....3159 Query Translation....3159 Synonyms....3159 Definition....3160 Historical Background....3160 Foundations....3160 Attribute Heterogeneity....3160 Predicate Heterogeneity....3160 Query Structure Heterogeneity....3160 Schema Matching for Attribute Heterogeneity....3161 Predicate Mapping for Predicate Heterogeneity....3161 Query Rewriting for Query Structure Heterogeneity....3162 Key Applications....3162 Vertical Integration Systems....3162 Meta Querying Systems....3163 Cross-References....3163 Recommended Reading....3163 Quorum Systems....3163 Synonyms....3163 Definition....3164 Historical Background....3165 Scientific Fundamentals....3165 Quorum Types and Their Sizes....3165 Availability....3167 Experimental....3167 Key Applications....3169 Future Directions....3169 Recommended Reading....3169 R....3171 Randomization Methods to Ensure Data Privacy....3171 Synonyms....3171 Definition....3171 Historical Background....3171 Foundations....3172 Local Randomization Techniques....3172 Privacy....3172 Algorithms....3173 Itemset Randomization....3173 Output Perturbation Techniques....3174 Privacy....3174 Algorithms....3174 Input Perturbation Techniques....3175 Privacy....3175 Algorithms....3175 Key Applications....3176 Future Directions....3176 Cross-References....3177 Recommended Reading....3177 Range Query....3177 Synonyms....3177 Definition....3178 Key Points....3178 Cross-References....3178 Rank-Aware Query Processing....3178 Synonyms....3178 Definition....3178 Historical Background....3178 Scientific Fundamentals....3179 Rank-Relational Algebra....3179 Rank-Relational Operators....3179 Ranking Algebraic Laws....3180 Physical Operators for Ranking....3181 Key Applications....3181 Cross-References....3181 Recommended Reading....3181 Ranked XML Processing....3182 Synonyms....3182 Definition....3182 Historical Background....3182 Threshold Algorithms....3183 XML and IR....3183 Foundations....3184 Scoring Structure....3184 Scoring Text....3186 XML Top-k Query Evaluation Techniques....3187 Key Applications....3188 Future Directions....3188 Experimental Results....3189 Data Sets....3189 URL to Code....3189 Cross-References....3189 Recommended Reading....3189 Ranking Views....3190 Synonyms....3190 Definition....3190 Historical Background....3190 Scientific Fundamentals....3190 Key Applications....3191 Cross-References....3191 Recommended Reading....3191 Rank-Join....3191 Definition....3191 Historical Background....3192 Scientific Fundamentals....3192 J*....3192 HRJN....3192 Optimal Rank-Joins....3193 Key Applications....3193 Cross-References....3193 Recommended Reading....3193 Rank-Join Indices....3194 Synonyms....3194 Definition....3194 Historical Background....3194 Scientific Fundamentals....3195 Key Applications....3197 Future Directions....3197 Experimental Results....3197 Cross-References....3198 Recommended Reading....3198 RDF Stores....3198 Synonyms....3198 Definition....3198 Historical Background....3198 Foundations....3199 Centralized RDF Stores....3199 Triple Stores....3199 Vertically Partitioned Tables....3200 Property Tables....3200 Graph Databases....3201 Distributed RDF Stores....3201 Data Storage....3201 Query Processing....3202 Key Applications....3202 Future Directions....3202 Experimental Results....3203 Datasets....3203 URL to Code....3203 Cross-References....3203 Recommended Reading....3203 RDF Technology....3204 Definition....3204 Historical Background....3205 Scientific Fundamentals....3205 Serialization Formats....3205 Query Language and RDF Stores....3206 Vocabularies and Ontology Languages....3206 Key Applications....3206 Cross-References....3207 Recommended Reading....3207 Real and Synthetic Test Datasets....3208 Synonyms....3208 Definition....3208 Historical Background....3208 Foundations....3208 Synthetic Datasets....3208 Real Datasets....3209 Datasets from Infrastructure-Based Generators....3209 Key Applications....3211 Future Directions....3211 Data Sets....3211 URL to Code....3212 Cross-References....3212 Recommended Reading....3212 Real-Time Transaction Processing....3212 Synonyms....3212 Definition....3212 Historical Background....3212 Foundations....3213 Transaction Model....3214 Concurrency Control....3214 Distributed Real-Time Transaction Processing....3215 Real-Time Two-Phase Commit....3215 Key Applications....3216 Future Directions....3216 Cross-References....3217 Recommended Reading....3217 Recall....3217 Definition....3217 Key Points....3218 Cross-References....3218 Receiver Operating Characteristic....3218 Synonyms....3218 Definition....3218 Historical Background....3218 Foundations....3218 Key Applications....3221 Future Directions....3221 URL to Code....3221 Cross-References....3222 Recommended Reading....3222 Recommender Systems....3222 Synonyms....3222 Definition....3222 Historical Background....3222 Scientific Fundamentals....3223 Collaborative Recommendation....3223 Content-Based Recommendation....3224 Hybrid Recommendation....3224 Key Applications....3225 Movie Recommendation....3225 Personalized Search Engines and News Feed....3225 Location-Based Services....3225 Data Sets....3225 MovieLens....3225 Netflix Prize....3225 Yahoo! Music....3225 URL to Code....3225 LensKit....3225 Apache Mahout....3225 RecDB....3225 Cross-References....3226 Recommended Reading....3226 Record Linkage....3226 Synonyms....3226 Definition....3226 Key Points....3226 Cross-References....3227 Recommended Reading....3227 Record Matching....3227 Synonyms....3227 Definition....3228 Historical Background....3228 Foundations....3229 String Similarity....3229 Record Matching....3230 Performance....3231 Key Applications....3232 Cross-References....3232 Recommended Reading....3232 Redundant Arrays of Independent Disks....3233 Synonyms....3233 Definition....3233 Key Points....3233 Cross-References....3234 Recommended Reading....3234 Reference Knowledge....3234 Definition....3234 Key Points....3234 Recommended Reading....3234 Region Algebra....3234 Definition....3234 Historical Background....3235 Foundations....3236 Key Applications....3238 Cross-References....3238 Recommended Reading....3238 Regulatory Compliance in Data Management....3239 Definition....3239 Historical Background....3239 Data Confidentiality....3239 Audits....3239 Data Retention....3239 Fundamentals....3240 Regulatory-Compliant Commercial Systems....3240 Write-Once Read-Many (WORM) Storage....3240 Trusted Hardware....3240 Software-Based Compliance Storage....3241 Regulatory-Compliant Data Management Systems Research....3241 Privacy-Preserving Data Publishing....3241 Data Confidentiality....3242 Verification of Computation....3242 Audit Logs....3242 Data Retention....3242 Key Applications....3243 Future Directions....3243 Cross References....3243 Recommended Reading....3243 Relational Algebra....3244 Definition....3244 Key Points....3244 Theorem....3245 Cross-References....3245 Recommended Reading....3245 Relational Calculus....3245 Synonyms....3245 Definition....3245 Key Points....3246 Cross-References....3247 Recommended Reading....3247 Relational Model....3247 Synonyms....3247 Definition....3247 Historical Background....3247 Foundations....3248 Intuitive View....3248 Conceptual View....3249 Implementation View....3249 Formal View....3250 Key Applications....3251 Cross-References....3252 Recommended Reading....3252 Relationships in Structured Text Retrieval....3252 Definition....3252 Key Points....3252 Cross-References....3252 Recommended Reading....3252 Relative Time....3253 Definition....3253 Key Points....3253 Cross-References....3253 Recommended Reading....3253 Relevance....3253 Synonyms....3253 Definition....3253 Key Points....3254 Cross-References....3255 Recommended Reading....3255 Relevance Feedback for Content-Based Information Retrieval....3255 Definition....3255 Historical Background....3255 Foundations....3255 General Assumptions....3255 Re-weighting Approaches....3256 Query Point Movement Approaches....3256 Machine Learning Approaches....3257 Key Applications....3257 Future Directions....3257 Cross-References....3257 Recommended Reading....3257 Relevance Feedback for Text Retrieval....3258 Synonyms....3258 Definition....3258 Key Points....3258 Cross-References....3259 Recommended Reading....3259 Replica Control....3259 Synonyms....3259 Definition....3259 Historical Background....3259 Scientific Fundamentals....3260 Key Applications....3264 Future Directions....3264 Cross-References....3265 Recommended Reading....3265 Replica Freshness....3266 Synonyms....3266 Definition....3266 Historical Background....3266 Foundations....3266 Value-Based Divergence....3267 Delay-Based Staleness....3267 Measures of Missed Updates....3267 Inter-Object Consistency Drift....3267 Transaction Semantics....3268 Mixed Measures....3268 Key Applications....3268 Future Directions....3268 Cross-References....3268 Recommended Reading....3268 Replicated Data Types....3269 Synonyms....3269 Definition....3269 Historical Background....3269 Foundations....3270 Encapsulating Replication and Concurrency....3270 CRDT Behavior....3270 Implementation Approaches and Requirements....3270 Example: OR-Set....3271 Usage....3272 Cross-References....3272 Recommended Readings....3272 Replicated Database Concurrency Control....3273 Synonyms....3273 Definition....3273 Key Points....3274 Cross-References....3274 Recommended Reading....3274 Replication....3275 Synonyms....3275 Definition....3275 Key Points....3275 Cross-References....3275 Replication Based on Group Communication....3275 Definition....3275 Historical Background....3276 Scientific Fundamentals....3276 Group Communication Primitives....3277 A Functional Model for Database Replication....3278 Deferred Update Database Replication Protocols....3279 Key Applications....3280 Future Directions....3280 Cross-References....3281 Recommended Reading....3281 Replication Based on Paxos....3282 Synonyms....3282 Definition....3282 Historical Background....3282 Scientific Fundamentals....3282 Key Applications....3284 Future Directions....3284 Recommended Reading....3284 Replication for Availability and Fault Tolerance....3285 Synonyms....3285 Definition....3285 Historical Background....3285 Scientific Fundamentals....3286 Basic Fault-Tolerance Architecture....3286 Replication for Performance and Fault Tolerance....3288 Network Partitions....3289 Other Failure Types....3290 Key Applications....3290 Future Directions....3291 Cross-References....3291 Recommended Reading....3291 Replication for Scalability....3292 Synonyms....3292 Definition....3292 Historical Background....3292 Foundations....3293 Attaining Atomicity and Isolation....3293 Transaction Mapping....3294 Consistency Criterion....3296 Key Applications....3297 Cross-References....3297 Recommended Reading....3297 Replication in Multitier Architectures....3298 Synonyms....3298 Definition....3298 Historical Background....3299 Foundations....3301 Cross-References....3304 Recommended Reading....3304 Replication with Snapshot Isolation....3305 Synonyms....3305 Definition....3305 Overview....3306 Historical Background....3306 Foundation: Snapshot Replication....3306 Key Applications....3307 Future Directions....3308 Cross-References....3308 Recommended Reading....3308 Reputation and Trust....3308 Synonyms....3308 Definition....3308 Key Points....3309 Cross-References....3309 Request Broker....3309 Synonyms....3309 Definition....3309 Historical Background....3309 Foundations....3310 Key Applications....3312 Future Directions....3312 Experimental Results....3312 URL to Code....3312 Cross-References....3312 Recommended Reading....3313 Residuated Lattice....3313 Synonyms....3313 Definition....3313 Key Points....3313 Cross-References....3314 Recommended Reading....3314 Resource Allocation Problems in Spatial Databases....3314 Synonyms....3314 Definition....3314 Historical Background....3315 Foundations....3315 Max-Inf Optimal-Location Query....3315 Min-Dist Optimal-Location Query....3317 Disk-Based k-Medoid Query....3318 Key Applications....3319 Location-Based Services....3319 Spatial Decision Making....3319 Future Directions....3319 Cross-References....3319 Recommended Reading....3319 Resource Description Framework....3319 Synonyms....3319 Definition....3319 Historical Background....3320 Scientific Fundamentals....3320 Key Applications....3321 Data Sets....3322 Cross-References....3322 Recommended Reading....3322 Resource Description Framework (RDF) Schema (RDFS)....3323 Synonyms....3323 Definition....3323 Key Points....3323 Cross-References....3326 Recommended Reading....3326 Resource Identifier....3326 Synonyms....3326 Definition....3326 Key Points....3326 Uniqueness....3327 Persistence....3327 Other Properties....3327 Cross-References....3327 Recommended Reading....3328 Result Display....3328 Synonyms....3328 Definition....3328 Key Points....3328 Cross-References....3329 Recommended Reading....3329 Retrospective Event Processing....3329 Definition....3329 Historical Background....3330 Foundations....3330 Key Applications....3330 Use Cases for Situation Reinforcement....3330 Anti-money Laundering....3330 The Greedy Seller Alert....3331 Monitored Patient Alert....3331 Use Cases for Retrospective Contexts....3331 Smart Retail....3331 Luggage Handling....3331 Utilities Billing System....3331 Use Cases for Patterns as Queries....3331 Stock Trends....3331 Fraud Detection in On-Line Gaming....3332 Inventory Management....3332 Cross-References....3332 Recommended Reading....3332 Reverse Nearest Neighbor Query....3332 Synonyms....3332 Definition....3333 Historical Background....3333 Foundations....3333 Key Applications....3336 Profile-Based Marketing....3336 Decision Support Systems....3336 Peer-to-Peer Systems....3336 Future Directions....3336 Experimental Results....3337 Datasets....3337 Cross-References....3337 Recommended Reading....3337 Reverse Top-k Queries....3337 Synonyms....3337 Definition....3338 Main Text....3338 Cross-References....3338 Recommended Reading....3338 Rewriting Queries Using Views....3339 Definition....3339 Historical Background....3339 Foundations....3339 Key Applications....3342 Cross-references....3342 Recommended Reading....3342 RMI....3342 Synonyms....3342 Definition....3342 Key Points....3342 Cross-References....3343 Recommended Reading....3343 Road Networks....3343 Synonyms....3343 Definition....3343 Historical Background....3344 Foundations....3345 Formal Definition of the Problem....3345 A Voronoi-Based Solution for Road-Networks....3347 Key Applications....3347 Future Directions....3347 Cross-References....3348 Recommended Reading....3348 Rocchio's Formula....3349 Definition....3349 Key Points....3349 Cross-References....3350 Recommended Reading....3350 Role-Based Access Control....3350 Synonyms....3350 Definition....3350 Historical Background....3350 Foundations....3351 RBAC0 Base Model....3351 RBAC1: RBAC with Role Hierarchy....3352 RBAC2: RBAC with Constraints....3352 RBAC3: The Consolidated Model....3353 Benefits of the RBAC Approach....3353 RBAC Standards....3353 Administration Models for RBAC....3354 RBAC Extensions....3354 Key Applications....3355 Future Directions....3355 URL to Code....3355 Cross-References....3355 Recommended Reading....3355 R-Precision....3356 Definition....3356 Key Points....3356 Cross-References....3356 R-Tree (and Family)....3356 Definition....3356 Historical Background....3356 Foundations....3357 Key Applications....3361 Geographic Information Systems....3361 Location-Based Services....3361 Multimedia Database Systems....3361 Future Directions....3361 Experimental Results....3362 Data Sets....3362 URL to Code....3362 Cross-References....3362 Recommended Reading....3362 Rule-Based Classification....3363 Definition....3363 Historical Background....3363 Foundations....3363 Using IF-THEN Rules for Classification....3363 Rule Ranking Measures....3364 Rule Induction....3365 Key Applications....3365 Future Directions....3366 Cross-References....3366 Recommended Reading....3366 S....3367 Safety and Domain Independence....3367 Synonyms....3367 Definition....3367 Historical Background....3367 Foundations....3368 Key Applications....3370 Future Directions....3370 Cross-References....3370 Recommended Reading....3370 Sagas....3371 Definition....3371 Key Points....3371 Cross-References....3371 Recommended Reading....3371 Sampling Techniques for Statistical Databases....3372 Definition....3372 Key Points....3372 Cross-References....3372 Recommended Reading....3372 SAN File System....3372 Synonyms....3372 Definition....3372 Key Points....3372 Cross-References....3373 Recommended Reading....3373 Scalable Decision Tree Construction....3373 Synonyms....3373 Definition....3373 Historical Background....3373 Foundations....3374 Problem Definition....3374 Data Access....3376 Tree Pruning....3377 PUBLIC Lower Bound....3378 Key Applications....3379 Recommended Reading....3379 Scheduler....3379 Synonyms....3379 Definition....3379 Key Points....3379 Cross-References....3380 Scheduling Strategies for Data Stream Processing....3380 Synonyms....3380 Definition....3380 Historical Background....3380 Foundations....3380 System Model....3380 Multiple CQ Scheduling....3381 Metrics and Strategies....3381 Key Applications....3384 Cross-References....3384 Recommended Reading....3385 Schema Evolution....3385 Definition....3385 Historical Background....3385 Foundations....3386 Key Applications....3386 Future Directions....3387 Cross-References....3387 Recommended Reading....3387 Schema Mapping....3387 Synonyms....3387 Definition....3387 Historical Background....3388 Foundations....3388 Semantics of Schema Mappings....3388 Definition....3388 Definition....3389 Types of Schema Mappings....3389 Sound, Complete, and Exact Mappings....3389 Global-as-View and Local-as-View....3390 Schema Mappings in Peer Data Sharing....3391 Creating Schema Mappings....3392 Data Translation....3394 Key Applications....3395 Cross-References....3395 Recommended Reading....3395 Schema Mapping Composition....3395 Synonyms....3395 Definition....3396 Historical Background....3396 Foundations....3397 Key Applications....3401 Cross-References....3401 Recommended Reading....3401 Schema Matching....3402 Synonyms....3402 Definition....3402 Historical Background....3402 Foundations....3403 State of the Art....3404 Key Applications....3406 Future Directions....3406 Cross-References....3406 Recommended Reading....3406 Schema Tuning....3406 Definition....3406 Historical Background....3406 Foundations....3407 Redundant Tables....3407 Key Applications....3407 Experimental Results....3407 Denormalization....3407 Materialized Views....3407 URL to Code and Data Sets....3408 Cross-References....3408 Recommended Reading....3408 Schema Versioning....3409 Definition....3409 Historical Background....3409 Foundations....3409 Types of Schema Evolution....3409 Practical and Theoretical Limits of Schema Versioning....3410 Completed Schemas....3410 Query Language Support....3410 Instance Amendment....3411 Future Directions....3411 Cross-References....3412 Recommended Reading....3412 Scientific Databases....3412 Definition....3412 Historical Background....3412 Foundations....3413 Measurement Framework....3413 Metadata Framework....3413 Summarization Framework....3414 Heterogeneity of Types....3414 Complexity and Heterogeneity of Formats....3414 Data Management Issues in Scientific Databases....3414 Traditional Issues....3414 Recent Trends....3415 Cross-References....3416 Recommended Reading....3416 Scientific Visualization....3417 Definition....3417 Key Points....3417 Cross-References....3418 Recommended Reading....3418 Scientific Workflows....3418 Synonyms....3418 Definition....3418 Historical Background....3418 Foundations....3419 Key Applications....3421 URL to Code....3422 Cross-References....3422 Recommended Reading....3422 Score Aggregation....3422 Recommended Reading....3423 Screen Scraper....3423 Synonyms....3423 Definition....3423 Key Points....3423 Cross-References....3424 Recommended Reading....3424 SCSI Target....3424 Definition....3424 Key Points....3424 Cross-References....3424 SDC Score....3424 Definition....3424 Key Points....3424 Cross-References....3425 Recommended Reading....3425 Search Engine Metrics....3426 Synonyms....3426 Definition....3426 Historical Background....3426 Foundations....3427 Relevance Judgments....3429 Hypothesis Testing and Relative Performance....3430 Key Applications....3430 Measuring Search Engine Performance....3430 Comparing Search Engines....3430 Optimizing Search Engine Performance....3430 Future Directions....3430 Data Sets....3430 Cross-References....3431 Recommended Reading....3431 Searching Digital Libraries....3431 Synonyms....3431 Definition....3431 Historical Background....3431 Foundations....3432 The Pre-Web Period....3432 The Early-Web Period....3432 The Web-Services Period....3433 Key Applications....3434 Cross-References....3434 Recommended Reading....3434 Second Normal Form (2NF)....3435 Synonyms....3435 Definition....3435 Key Points....3435 Cross-References....3435 Recommended Reading....3435 Secondary Index....3435 Synonyms....3435 Definition....3436 Key Points....3436 Cross-References....3436 Recommended Reading....3436 Secure Data Outsourcing....3436 Synonyms....3436 Definition....3437 Historical Background....3437 Foundations....3437 Security Requirements in Secure Data Outsourcing....3438 Techniques for Secure Data Outsourcing....3439 Key Applications....3442 Future Directions....3442 Cross-References....3443 Recommended Reading....3443 Secure Database Development....3444 Synonyms....3444 Definition....3444 Historical Background....3444 Foundations....3444 General Secure Database Systems....3445 Secure Database Development Using Patterns....3445 Secure Database Development Using UMLsec....3446 Applications Including Secure Databases....3447 Designing Secure Databases Using OCL....3447 Other Approaches to Secure Software Development with Applicability to Databases....3448 System Architecture for Security....3449 Key Applications....3449 Cross-References....3450 Recommended Reading....3450 Secure Multiparty Computation Methods....3450 Definition....3450 Historical Background....3451 Foundations....3451 Secure Sum....3453 Secure Comparison/Yao's Millionaire Problem....3453 Dot Product Protocol....3453 Oblivious Evaluation of Polynomials....3453 Privately Computing ln x....3454 Secure Intersection....3454 Secure Set Union....3454 Key Applications....3454 Classification....3454 Association Rule Mining....3455 Clustering....3455 Outlier Detection....3455 Future Directions....3455 Cross-References....3456 Recommended Reading....3456 Secure Transaction Processing....3456 Synonyms....3456 Definition....3456 Historical Background....3456 Scientific Fundamentals....3457 Key Applications....3465 Cross-References....3465 Recommended Reading....3465 Security Services....3467 Synonyms....3467 Definition....3467 Key Points....3467 Cross-References....3468 Recommended Reading....3468 Selection....3469 Synonyms....3469 Definition....3469 Key Points....3469 Cross-References....3469 Selectivity Estimation....3469 Synonyms....3469 Definition....3470 Key Points....3470 Cross-References....3470 Recommended Reading....3470 Self-Maintenance of Views....3470 Definition....3470 Key Points....3471 Cross-References....3472 Recommended Reading....3472 Self-Management Technology in Databases....3472 Synonyms....3472 Definition....3472 Historical Background....3473 Foundations....3473 General Framework....3473 Self-Management Paradigms....3475 Infrastructure....3477 Future Directions....3477 Cross-References....3478 Recommended Reading....3478 Semantic Atomicity....3479 Synonyms....3479 Definition....3479 Historical Background....3479 Scientific Fundamentals....3479 Key Applications....3483 Cross-References....3483 Recommended Reading....3483 Semantic Crowdsourcing....3484 Synonyms....3484 Definition....3484 How about Concepts and Applications?....3484 Recommended Reading....3485 Semantic Data Integration for Life Science Entities....3485 Synonyms....3485 Definition....3485 Historical Background....3486 Foundations....3486 Identity Versus Similarity....3486 Naming Standards....3487 Evolution of Names....3488 Key Applications....3488 Semantic Integration of Entities....3488 Entity Identification in Text....3488 URL to Code....3488 Cross-References....3489 Recommended Reading....3489 Semantic Data Model....3489 Synonyms....3489 Definition....3489 Key Points....3489 Cross-References....3491 Recommended Reading....3491 Semantic Matching....3491 Definition....3491 Historical Background....3492 Foundations....3493 Key Applications....3496 Future Directions....3496 Experimental Results....3496 Data Sets....3497 URL to Code....3497 Cross-References....3497 Recommended Reading....3497 Semantic Modeling and Knowledge Representation for Multimedia Data....3497 Synonyms....3497 Definition....3497 Historical Background....3498 Foundations....3499 Semantic Modeling....3499 Knowledge Representation....3500 Key Applications....3502 Future Directions....3502 Cross-References....3502 Recommended Reading....3502 Semantic Modeling for Geographic Information Systems....3503 Synonyms....3503 Definition....3503 Historical Background....3504 Foundations....3504 Requirements for Semantic Modeling of Spatial Data....3504 Survey of Current Semantic Modeling Approaches....3507 Key Applications....3507 Future Directions....3507 Cross-References....3508 Recommended Reading....3508 Semantic Overlay Networks....3508 Synonyms....3508 Definition....3508 Historical Background....3509 Foundations....3509 Key Applications....3512 Future Directions....3512 Cross-References....3512 Recommended Reading....3512 Semantic Social Web....3513 Synonyms....3513 Definition....3513 Historical Background....3513 Foundations....3514 Core Vocabularies....3514 Core Social Vocabularies....3514 Interconnecting Vocabularies....3515 Domain-Specific Vocabularies....3515 Query Language....3515 Key Applications....3515 Data Sharing....3515 Knowledge Creation and Sharing....3515 Social Tagging....3516 Social Networks....3516 Interlinking of Online Communities....3516 Cross-References....3517 Recommended Reading....3517 Semantic Streams....3517 Synonyms....3517 Definition....3517 Historical Background....3517 Scientific Fundamentals....3518 Key Applications....3521 Future Directions....3521 Experimental Results....3522 Datasets....3522 URL to CODE....3522 Cross-References....3522 Recommended Reading....3522 Semantic Web....3523 Definition....3523 Historical Background....3524 Foundations....3524 RDF Basic Features....3525 RDF Schema Basic Features....3525 Key Applications....3526 Future Directions....3526 Cross-References....3527 Recommended Reading....3527 Semantic Web Query Languages....3527 Synonyms....3527 Definition....3527 Historical Background....3527 Foundations....3528 Key Applications....3529 Future Directions....3530 Data Sets....3530 URL to Code....3531 Cross-References....3531 Recommended Reading....3531 Semantic Web Services....3531 Definition....3531 Key Points....3532 Cross-References....3532 Recommended Reading....3533 Semantics-Based Concurrency Control....3533 Definition....3533 Key Points....3533 Cross-References....3534 Recommended Reading....3534 Semijoin....3534 Synonyms....3534 Definition....3534 Historical Background....3534 Foundations....3534 Relational Definition....3534 Semijoin Filtering....3535 Bit Vector Filtering....3536 Key Applications....3537 Experimental Results....3537 Cross-References....3538 Recommended Reading....3538 Semijoin Program....3538 Synonyms....3538 Definition....3538 Historical Background....3538 Foundations....3539 Cyclic and Acyclic Query Hyper-graphs....3539 Reducer and Full Reducer....3539 Semijoins, Distributed Query Optimization and Semijoin Programs....3540 Key Applications....3541 Cross-References....3541 Recommended Reading....3541 Semi-structured Data....3542 Synonyms....3542 Definition....3542 Historical Background....3542 Foundations....3543 Key Applications....3544 Cross-References....3544 Recommended Reading....3544 Semi-structured Data Model....3544 Synonyms....3544 Definition....3544 Definition 1....3545 Historical Background....3545 Foundations....3545 Definition 2....3548 Definition 3....3548 Key Applications....3548 Cross-References....3548 Recommended Reading....3549 Semi-structured Database Design....3549 Synonyms....3549 Definition....3549 Historical Background....3549 Foundations....3549 Key Applications....3554 Future Directions....3554 Cross-References....3554 Recommended Reading....3554 Semi-structured Query Languages....3555 Definition....3555 Historical Background....3555 Foundations ....3555 Key Applications....3557 Cross-References....3557 Recommended Reading....3557 Semi-supervised Learning....3557 Synonyms....3557 Definition....3557 Historical Background....3558 Foundations....3558 Key Applications....3560 Cross-References....3560 Recommended Reading....3560 Sensor Networks....3561 Synonyms....3561 Definition....3561 Historical Background....3561 Foundations....3561 Data-Centric Techniques in Sensor Networks....3563 Key Applications....3564 Future Directions....3564 Cross-References....3564 Recommended Reading....3564 Sequenced Semantics....3565 Definition....3565 Key Points....3565 S-Reducibility....3566 Extended S-Reducibility....3566 Interval Preservation....3566 Cross-References....3567 Recommended Reading....3567 Sequential Patterns....3567 Synonyms....3567 Definition....3567 Historical Background....3568 Foundations....3568 Sequence Data Format....3569 Search Strategy....3569 Search Space Pruning....3570 Pattern Closure Checking Scheme....3571 Key Applications....3571 Frequent Subsequence-Based Classifier....3571 Operating System and Software Engineering....3571 Frequent Subsequence-Based XML Data Management....3571 Web Log Data Mining....3571 Experimental Results....3572 Data Sets....3572 URL to Code....3572 Cross-References....3572 Recommended Reading....3572 Serializability....3573 Synonyms....3573 Definition....3573 Main Text....3573 Cross-References....3574 Recommended Reading....3574 Serializable Snapshot Isolation....3574 Synonyms....3574 Definition....3574 Historical Background....3575 Scientific Fundamentals....3575 Key Applications....3576 Future Directions....3577 Cross-References....3577 Recommended Reading....3577 Service Component Architecture (SCA)....3577 Synonyms....3577 Definition....3577 Key Points....3578 Cross-References....3578 Recommended Reading....3578 Service-Oriented Architecture....3578 Synonyms....3578 Definition....3578 Historical Background....3578 Foundations....3579 Key Applications....3581 Future Directions....3581 Cross-References....3581 Recommended Reading....3582 Session....3582 Synonyms....3582 Definition....3582 Key Points....3582 Cross-References....3582 Recommended Reading....3582 Shared-Disk Architecture....3582 Definition....3582 Key Points....3583 Cross-References....3583 Shared-Memory Architecture....3583 Synonyms....3583 Definition....3583 Key Points....3583 Cross-References....3584 Shared-Nothing Architecture....3584 Synonyms....3584 Definition....3584 Key Points....3584 Cross-References....3585 Side-Effect-Free View Updates....3585 Definition....3585 Historical Background....3585 Foundations....3585 Key Applications....3588 Cross-References....3588 Recommended Reading....3588 Signature Files....3589 Definition....3589 Historical Background....3589 Foundations....3589 Bit-Slice Signature File....3591 Signature Trees....3592 Key Applications....3593 Cross-References....3593 Recommended Reading....3593 Similarity and Ranking Operations....3593 Synonyms....3593 Definition....3593 Historical Background....3594 Foundations....3594 Associative Similarity....3595 Probabilistic Retrieval....3596 Related Areas....3597 Key Applications....3598 Cross-References....3598 Recommended Reading....3598 Simplicial Complex....3598 Synonyms....3598 Definition....3599 Historical Background....3599 Foundations....3600 Key Applications....3603 Future Directions....3603 Cross-References....3604 Recommended Reading....3604 Singular Value Decomposition....3604 Synonyms....3604 Definition....3604 Key Points....3605 Cross-References....3606 Recommended Reading....3606 Skyline Queries and Pareto Optimality....3606 Synonyms....3606 Definition....3606 Historical Background....3607 Scientific Fundamentals....3608 Key Applications....3609 Future Directions....3609 Data Sets....3609 Cross References....3609 Recommended Reading....3609 Snapshot Equivalence....3610 Synonyms....3610 Definition....3610 Key Points....3610 Cross-References....3610 Recommended Reading....3611 Snapshot Isolation....3611 Synonyms....3611 Definition....3611 Historical Background....3611 Foundations....3612 Key Applications....3615 Future Directions....3616 Cross-References....3616 Recommended Reading....3616 Snippet....3617 Synonyms....3617 Definition....3617 Key Points....3617 Recommended Reading....3618 Snowflake Schema....3618 Synonyms....3618 Definition....3618 Key Points....3618 Cross-References....3619 Recommended Reading....3619 SOAP....3619 Definition....3619 Key Points....3619 Cross-References....3620 Recommended Reading....3620 Social Applications....3620 Synonyms....3620 Definition....3620 Key Points....3620 Cross-References....3621 Social Influence....3621 Synonyms....3621 Definition....3621 Historical Background....3621 Scientific Fundamentals....3621 The Threshold Model....3622 The Cascade Model....3622 Extensions....3622 Discovering the Underlying Graph....3623 Key Applications....3623 Influential Individuals....3623 Influential Groups....3624 Bursty Subgraphs....3625 Datasets....3625 URL to Code....3625 Cross-References....3625 Recommended Reading....3626 Social Media Analysis....3626 Synonyms....3626 Definition....3626 Historical Background....3627 Scientific Fundamentals....3627 Data....3627 Data Analysis Tasks....3628 Key Applications....3629 Cross-References....3629 Recommended Reading....3629 Social Media Analytics....3630 Definition....3630 Text Analytics in Social Media....3630 Structure Analytics in Social Media....3630 Temporal Analytics in Social Media....3631 Interactive Analytics in Social Media....3631 Social Media Harvesting....3631 Definition....3631 Historical Background....3631 Key Applications....3631 Event Detection/Visualization/Tracking....3631 Trending Topics Summarization....3633 User Profiling....3633 Recommended Reading....3635 Social Networks....3635 Definition....3635 Historical Background....3635 Foundations....3636 Types....3636 Notation....3636 Measures....3636 Socio-Centric Properties....3637 Ego-Centric Properties....3637 Subgroups....3638 Topological Properties....3638 Small-World Topology....3638 Creation of Networks....3638 Key Applications....3639 Distributed Information Management....3639 Information Extraction....3639 Social Recommendations....3639 Future Directions....3639 Data Sets....3640 URL to Code....3640 Tools and Libraries....3640 Cross-References....3640 Recommended Reading....3640 Software Transactional Memory....3641 Definition....3641 Key Points....3641 Cross-References....3642 Recommended Reading....3642 Software-as-a-Service (SaaS)....3642 Synonyms....3642 Definition....3642 Overview....3642 Cross-References....3643 Software-Defined Storage....3643 Synonyms....3643 Definition....3643 Main Text....3643 Recommended Reading....3643 Solid State Drive (SSD)....3643 Synonyms....3643 Definition....3644 Main Text....3644 Recommended Reading....3644 Sort-Merge Join....3644 Synonyms....3644 Definition....3644 Key Points....3644 Cross-References....3645 Recommended Reading....3645 Space-Filling Curves....3645 Synonyms....3645 Definition....3645 Key Points....3646 Cross-References....3646 Recommended Reading....3646 Space-Filling Curves for Query Processing....3646 Synonyms....3646 Definition....3646 Historical Background....3646 Foundations....3647 Mapping Scheme....3647 The Peano SFC....3647 The Gray SFC....3648 The Hilbert SFC....3648 Segment Types....3649 Irregularity....3650 Key Applications....3650 Preprocessing for Multidimensional Applications: Multimedia Databases, GIS, and Multidimensional Indexing....3650 Network-Attached Storage Devices (NASDs)....3651 Multimedia Disk Scheduling....3651 Future Directions....3651 Cross-References....3651 Recommended Reading....3651 SPARQL....3652 Synonyms....3652 Scientific Fundamentals....3652 Definition....3652 Historical Background....3652 Foundations....3652 Syntax....3652 Semantic....3653 Key Applications....3656 Knowledge Graph Application....3656 Graph Database....3656 Future Directions....3656 Cross-References....3656 Recommended Reading....3656 Sparse Index....3656 Synonyms....3656 Definition....3656 Key Points....3657 Cross-References....3657 Recommended Reading....3657 Spatial and Spatiotemporal Data Models and Languages....3657 Definition....3657 Historical Background....3658 Foundations....3658 Key Applications....3661 Cross-References....3661 Recommended Reading....3661 Spatial Anonymity....3662 Synonyms....3662 Definition....3662 Historical Background....3662 Foundations....3664 Key Applications....3666 Future Directions....3667 Experimental Results....3667 Cross-References....3667 Recommended Reading....3668 Spatial Data Analysis....3668 Synonyms....3668 Definition....3668 Historical Background....3669 Foundations....3669 Key Applications....3671 Future Directions....3673 Cross-References....3673 Recommended Reading....3673 Spatial Data Mining....3673 Synonyms....3673 Definition....3673 Historical Background....3674 Foundations....3674 Key Applications....3678 Future Directions....3679 Cross-References....3680 Recommended Reading....3680 Spatial Data Types....3681 Synonyms....3681 Definition....3681 Historical Background....3681 Foundations....3682 Key Applications....3684 Cross-References....3685 Recommended Reading....3685 Spatial Datawarehousing....3685 Definition....3685 Historical Background....3686 Scientific Fundamentals....3687 Spatial Dimensions and Facts....3687 Types of Spatial Hierarchies....3687 Spatiality and Measures....3688 Trajectory Data Warehouses....3688 Key Applications....3688 Future Directions....3689 Cross-References....3689 Recommended Reading....3689 Spatial Indexing Techniques....3690 Synonyms....3690 Definition....3690 Historical Background....3691 Foundations....3691 Indices for Multidimensional Points....3691 Indices for Multidimensional Regions....3692 Key Applications....3695 Experimental Results....3695 Datasets....3695 URL to Code....3695 Cross-References....3695 Recommended Reading....3696 Spatial Join....3696 Definition....3696 Historical Background....3697 Foundations....3697 Early Spatial Join Algorithms....3697 The R-Tree Join....3697 Algorithms that Do Not Consider Indexes....3698 Spatial Hash Join....3698 Partition Based Spatial Merge Join....3699 Size Separation Spatial Join....3700 Scalable Sweeping-Based Spatial Join....3701 Single-Index Join Methods....3701 Indexed Nested Loops Join....3701 Seeded Tree Join....3701 Build and Match....3702 Sort and Match....3702 Slot Index Spatial Join....3702 Comparison of Spatial Join Algorithms....3702 Key Applications....3703 Spatial Database Systems....3703 Geographic Information Systems....3703 Data Mining....3703 Cross-References....3703 Recommended Reading....3704 Spatial Matching Problems....3704 Definition....3704 Historical Background....3705 Scientific Fundamentals....3705 Key Applications....3706 Future Directions....3706 Data Sets....3706 URL to Code....3706 Cross-References....3706 Recommended Reading....3706 Spatial Network Databases....3707 Synonyms....3707 Definition....3707 Foundations....3707 Data Model of Spatial Networks....3707 Key Applications....3710 Location-Based Services....3710 Emergency Planning....3710 Future Directions....3711 Cross-References....3711 Recommended Reading....3711 Spatial Operations and Map Operations....3712 Synonyms....3712 Definition....3712 Historical Background....3712 Foundations....3713 Spatial Operations....3713 Map Operations....3713 Other Operations....3713 Key Applications....3719 Cross-References....3719 Recommended Reading....3719 Spatial Queries in the Cloud....3719 Definition....3719 Historical Background....3719 Scientific Fundamentals....3720 Key Applications....3724 Geographic Information System....3724 Analytical Medical Imaging....3724 Location-Based Services....3724 Future Directions....3724 Experimental Results....3724 Datasets....3724 URL to Code....3724 Cross-References....3725 Recommended Reading....3725 Spatial-Keyword Search....3725 Synonyms....3725 Definition....3725 Historical Background....3725 Scientific Fundamentals....3726 Key Applications....3729 Future Directions....3730 Cross-References....3730 Recommended Readings....3730 Spatiotemporal Data Mining....3731 Synonyms....3731 Definition....3731 Historical Background....3731 Foundations....3732 Clustering....3732 Classification and Prediction....3734 Pattern Extraction....3734 Key Applications....3736 Traffic Analysis....3736 Studying the Movement Behavior of Animals....3736 Video Analysis....3736 Cross-References....3736 Recommended Reading....3737 Spatiotemporal Data Types....3737 Synonyms....3737 Definition....3737 Key Points....3737 Cross-References....3738 References....3738 Spatiotemporal Data Warehouses....3738 Synonyms....3738 Definition....3738 Historical Background....3739 Foundations....3740 Key Applications....3742 Traffic Control....3742 Mobile Computing....3742 Sensor Systems....3743 Future Directions....3743 Experimental Results....3743 Data Sets....3743 Cross-References....3743 Recommended Reading....3743 Spatiotemporal Interpolation Algorithms....3744 Synonyms....3744 Definition....3744 Historical Background....3744 Foundations....3744 Key Applications....3746 Future Directions....3747 Cross-References....3747 Recommended Reading....3747 Spatiotemporal Selectivity Estimation....3748 Synonyms....3748 Definition....3748 Historical Background....3748 Foundations....3749 Selectivity Estimation for STWQ....3749 Selectivity Estimation for STDJQ....3749 Key Applications....3750 Future Directions....3750 Cross-References....3750 Recommended Reading....3750 Spatiotemporal Trajectories....3751 Synonyms....3751 Definition....3751 Historical Background....3751 Foundations....3752 Key Applications....3754 Future Directions....3755 Experimental Results....3755 Data Sets....3755 Url to Code....3755 Cross-References....3755 Recommended Reading....3755 Specialization and Generalization....3756 Synonyms....3756 Definition....3756 Key Points....3756 Cross-References....3757 Recommended Reading....3757 Specificity....3757 Synonyms....3757 Definition....3757 Key Points....3757 Cross-References....3758 Recommended Reading....3758 Spectral Clustering....3758 Synonyms....3758 Definition....3758 Historical Background....3759 Foundations....3759 Key Applications....3762 Cross-References....3762 Recommended Reading....3762 Split....3763 Synonyms....3763 Definition....3763 Key Points....3763 Cross-References....3763 Split Transactions....3763 Definition....3763 Key Points....3763 Cross-References....3764 Recommended Reading....3764 SQL....3764 Synonyms....3764 Definition....3765 Historical Background....3765 Early Language Development....3765 Standards....3766 Foundations....3767 Queries....3767 Data Manipulation....3768 Database Administration....3769 Advanced Features....3770 Criticisms....3771 Key Applications....3771 Cross-References....3772 Recommended Reading....3772 SQL Analytics on Big Data....3773 Synonyms....3773 Definition....3773 Scientific Fundamentals....3773 Evolution of Big Data Analytics....3773 Overview of Representative Systems....3774 Hive....3775 Apache Impala....3775 Big SQL....3776 Spark SQL....3777 Update-Optimized SQL Engines....3777 Key Applications....3778 Cross-References....3778 Recommended Reading....3778 SQL Isolation Levels....3779 Synonyms....3779 Definition....3779 Key Points....3780 Cross-References....3781 Recommended Reading....3781 SQL-Based Temporal Query Languages....3781 Definition....3781 Historical Background....3781 Foundations....3782 Approach I: Abstract Data Types – SQL/ATD....3783 Approach II: Folding and Unfolding – IXSQL....3783 Approach III: Point Timestamps – SQL/TP....3784 Approach IV: Syntactic Defaults – TSQL2....3785 Approach V: Statement Modifiers – ATSQL....3786 Approach VI: Temporal Expressions – TempSQL....3786 Key Applications....3787 Future Directions....3787 Cross-References....3787 Recommended Reading....3787 Stable Distribution....3788 Synonyms....3788 Definition....3788 Historical Background....3788 Foundations....3789 Stable Random Projections....3789 Statistical Estimations....3789 Sample Complexity....3790 Sampling from Stable Distributions....3790 Key Applications....3791 Stable Random Projections for Dimension Reductions....3791 Stable Random Projections for Data Stream Computations....3791 Cross-References....3792 Recommended Reading....3792 Stack-Based Query Language....3792 Synonyms....3792 Definition....3792 Key Points....3793 Cross-References....3793 Recommended Reading....3793 Staged DBMS....3794 Synonyms....3794 Definition....3794 Historical Background....3794 Foundations....3794 Key Applications....3795 Future Directions....3797 Cross-References....3797 Recommended Reading....3797 Standard Effectiveness Measures....3798 Synonyms....3798 Definition....3798 Historical Background....3798 Foundations....3798 Experimental Setup....3798 Recall and Precision....3799 F-Measure....3799 Precision-Recall Curve....3799 Average Precision....3800 ROC Curve....3800 Key Applications....3800 Data Sets....3800 Cross-References....3800 Recommended Reading....3801 Star Index....3801 Synonyms....3801 Definition....3801 Key Points....3801 Cross-References....3801 Star Schema....3801 Synonyms....3801 Definition....3801 Key Points....3801 Cross-References....3802 Recommended Reading....3802 State-Based Publish/Subscribe....3802 Definition....3802 Key Points....3802 Cross-References....3804 Recommended Reading....3804 Statistical Data Management....3804 Synonyms....3804 Definition....3804 Key Points....3804 Cross-References....3805 Recommended Reading....3805 Statistical Disclosure Limitation for Data Access....3805 Synonyms....3805 Definition....3805 Historical Background....3805 Foundations....3806 Privacy, Confidentiality, and Individual Identification....3806 The Intruder....3806 Statistical Analysis Methods for Protecting Privacy....3807 Putting SDL Methods to Use: Risk-Utility Tradeoff....3808 Summary....3811 Key Applications....3811 Future Directions....3811 Cross-References....3812 Recommended Reading....3812 Steganography....3812 Synonyms....3812 Definition....3812 Key Points....3813 Steganography Versus Watermarking....3813 Fingerprinting....3813 Recommended Reading....3813 Stemming....3813 Synonyms....3813 Definition....3813 Historical Background....3813 Foundations....3814 Definitions....3814 Stemming Algorithms....3815 Prefixes and Infixes....3816 Performance and Evaluation....3816 Non-English Stemmers....3817 Key Applications....3817 Data Sets....3817 URL to Code....3817 Cross-References....3817 Recommended Reading....3817 Stop-&-Go Operator....3818 Synonyms....3818 Definition....3818 Key Points....3818 Cross-References....3818 Recommended Reading....3818 Stoplists....3819 Synonyms....3819 Definition....3819 Key Points....3819 Cross-References....3820 Recommended Reading....3820 Storage Access Models....3820 Synonyms....3820 Definition....3821 Historical Background....3821 Foundations....3821 Key Applications....3822 Cross-References....3822 Recommended Reading....3822 Storage Area Network....3822 Synonyms....3822 Definition....3822 Key Points....3823 Cross-References....3823 Recommended Reading....3823 Storage Consolidation....3823 Definition....3823 Key Points....3823 Cross-References....3823 Storage Devices....3824 Synonyms....3824 Definition....3824 Historical Background....3824 Foundations....3824 Key Applications....3825 Cross-References....3825 Recommended Reading....3825 Storage Grid....3826 Synonyms....3826 Definition....3826 Key Points....3826 Cross-References....3827 Recommended Reading....3827 Storage Management....3828 Definition....3828 Historical Background....3828 Foundations....3828 General Classification of Storage Management Functions....3828 Elemental Technologies of Storage Management....3829 Key Applications....3830 Future Directions....3831 Integration of Management Software Including Storage Management....3831 Visualization and Optimization from a Business Viewpoint....3831 Establishing Framework for Management Applications....3831 URL to CODE....3832 Cross-References....3832 Recommended Reading....3832 Storage Management Initiative Specification....3832 Synonyms....3832 Definition....3832 Key Points....3833 Cross-References....3834 Recommended Reading....3834 Storage Manager....3834 Synonyms....3834 Definition....3834 Historical Background....3834 Foundations....3835 Storage Layer Concepts....3835 Storage Layer Services....3835 Storage Layer Requirements....3836 Storage Layer Components....3836 On-Disk Data Structures....3836 In-Memory Data Structures....3837 Query and Update Processing....3837 Concurrency Control....3837 Logging and Recovery....3838 Utilities....3838 Key Applications....3838 Future Directions....3838 Queuing....3838 XML Support....3838 Transactional Memory....3838 Self-Tuning, Self-Repair, Total Cost of Ownership....3839 Cross-References....3839 Recommended Reading....3839 Storage Network Architectures....3839 Definition....3839 Historical Background....3839 Foundations....3840 Key Applications....3842 Cross-References....3843 Recommended Reading....3843 Storage Networking Industry Association....3843 Synonyms....3843 Definition....3843 Key Points....3844 Cross-References....3844 Recommended Reading....3844 Storage of Large Scale Multidimensional Data....3844 Synonyms....3844 Definition....3844 Historical Background....3844 Foundations....3845 Efficient Storage of Large Multidimensional Data....3845 Data Export to Tertiary Storage Media....3846 Data Retrieval....3846 Techniques for Reducing Tertiary Storage Access Time....3847 Super-Tile Concept....3847 Clustering....3848 Caching....3849 Conclusion....3849 Key Applications....3849 Cross-References....3849 Recommended Reading....3849 Storage Power Management....3850 Definition....3850 Historical Background....3850 Foundations....3850 Key Applications....3851 Cross-References....3852 Recommended Reading....3852 Storage Protection....3852 Synonyms....3852 Definition....3852 Historical Background....3852 Foundations....3853 Key Applications....3853 Cross-References....3853 Recommended Reading....3854 Storage Protocols....3854 Synonyms....3854 Definition....3854 Historical Background....3854 Foundations....3854 Key Applications....3856 Cross-References....3857 Recommended Reading....3857 Storage Resource Management....3857 Synonyms....3857 Definition....3857 Key Points....3857 Cross-References....3857 Recommended Reading....3858 Storage Security....3858 Synonyms....3858 Definition....3858 Historical Background....3858 Foundations....3858 Key Applications....3860 Cross-References....3860 Recommended Reading....3860 Storage Virtualization....3860 Definition....3860 Key Points....3861 Cross-References....3861 Recommended Reading....3861 Stored Procedure....3862 Definition....3862 Key Points....3862 Cross-References....3862 Stream Mining....3862 Synonyms....3862 Definition....3862 Historical Background....3863 Foundations....3863 Key Applications....3864 Future Directions....3864 Experimental Results....3865 Data Sets....3865 URL to Code....3865 Cross-References....3865 Recommended Reading....3865 Stream Models....3866 Definition....3866 Historical Background....3866 Foundations....3866 Basic Model Definitions....3866 Examples and Extensions of Basic Models....3867 Key Applications....3868 Future Directions....3868 Cross-References....3868 Recommended Reading....3868 Stream Processing....3869 Synonyms....3869 Definition....3869 Key Points....3869 Cross-References....3870 Recommended Reading....3870 Stream Processing on Modern Hardware....3870 Definition....3870 Historical Background....3870 Scientific Fundamentals....3871 Streaming Systems on Multi-core CPUs....3871 Streaming Systems on GPUs....3872 Streaming Systems on FPGA....3873 Key Applications....3873 High-Performance Real-Time Data Processing....3873 Cross-References....3874 Recommended Reading....3874 Stream Reasoning....3874 Synonyms....3874 Definition....3874 Historical Background....3874 Scientific Fundamentals....3875 Expressivity....3876 Distribution and Heterogeneity....3876 Scalability....3877 Benchmarking and Comparison....3878 Key Applications....3878 Web of Things....3878 Smart Cities....3878 Social Media Analysis....3879 Location-Aware Services and Mobile Applications....3879 Smart Building and Resource Optimization....3879 Emergency Management....3879 Future Directions....3879 Cross-References....3879 Recommended Reading....3880 Stream Sampling....3880 Definition....3880 Historical Background....3880 Foundations....3880 Reservoir Sampling....3881 Sample and Count....3882 Distinct Sampling....3882 Time-Decayed Sampling....3883 Handling Deletions....3884 Key Applications....3884 Cross-References....3885 Recommended Reading....3885 Stream Similarity Mining....3885 Synonyms....3885 Definition....3885 Historical Background....3886 Foundations....3886 Estimating the L2 Distance....3886 Estimating the Lp Distance: p-Stable Distributions....3887 Approximating Jaccard Similarity: Min-Wise Hashing....3888 Sliding Windows....3889 Lower Bounds for Stream Distance....3890 Key Applications....3890 Tracking Change in Network Traffic....3890 Query Optimization....3890 Processing Genetic Data....3890 Data Mining....3890 Cross-References....3891 Recommended Reading....3891 Streaming Analytics....3891 Data Pre-processing and Transformation....3892 Modeling and Evaluation....3894 Conclusion....3897 Recommended Reading....3897 Streaming Applications....3899 Synonyms....3899 Definition....3899 Key Points....3899 Cross-References....3900 Recommended Reading....3900 Stream-Oriented Query Languages and Operators....3900 Synonyms....3900 Definition....3900 Historical Background....3901 Foundations....3901 Key Applications....3906 Cross-References....3906 References....3907 Strong Consistency Models for Replicated Data....3907 Synonyms....3907 Definition....3907 Historical Background....3907 Foundations....3908 Key Applications....3910 Future Directions....3910 Cross-References....3910 Recommended Reading....3910 Structural Indexing....3911 Synonyms....3911 Definition....3911 Historical Background....3911 Foundations....3912 Semi-structured Data Example....3912 Axis Graph Definition....3913 Structural Summary Definition....3913 Sample Structural Summaries....3913 AxPRE Summary Definition....3914 Sample AxPRE Summaries....3915 Summary Lattice....3915 Key Applications....3915 Future Directions....3915 Cross-References....3915 Recommended Reading....3915 Structure Analytics in Social Media....3916 Synonyms....3916 Definition....3916 Historical Background....3916 Foundations....3917 Key Applications....3918 Future Directions....3919 Cross-References....3919 Recommended Reading....3919 Structure Weight....3919 Definition....3919 Key Points....3920 Cross-References....3920 Recommended Reading....3920 Structured Data in Peer-to-Peer Systems....3920 Synonyms....3920 Definition....3921 Historical Background....3921 Foundations....3921 Unstructured P2P Systems....3921 Structured P2P Systems....3921 Key Applications....3924 Future Directions....3924 Cross-References....3925 Recommended Reading....3925 Structured Document Retrieval....3925 Synonyms....3925 Definition....3925 Key Points....3925 Cross-References....3926 Recommended Reading....3927 Structured Text Retrieval Models....3927 Synonyms....3927 Definition....3927 Historical Background....3927 Foundations....3928 Explicit vs. Implicit Structure....3928 Static vs. Dynamic Structure....3928 Single Hierarchy vs. Multiple Hierarchies....3929 Exact Matching Versus Ranking....3929 Key Applications....3930 Cross-References....3930 Recommended Reading....3930 Subject Spaces....3931 Definition....3931 Key Points....3931 Cross-References....3932 Recommended Reading....3932 Subspace Clustering Techniques....3932 Synonyms....3932 Definition....3932 Historical Background....3932 Scientific Fundamentals....3933 Different Challenges: The ``Curse of Dimensionality''....3933 Different Solutions: Categories of Subspace Clustering Techniques....3933 Axis-Parallel Subspaces....3933 Pattern-Based Clustering....3934 Correlation Clustering....3934 Key Applications....3935 Future Directions....3935 Url To Code....3935 Cross-References....3935 Recommended Reading....3935 Success at n....3936 Synonyms....3936 Definition....3936 Key Points....3936 Cross-References....3936 Succinct Constraints....3936 Definition....3936 Key Points....3936 Cross-References....3937 Recommended Reading....3937 Suffix Tree....3937 Synonyms....3937 Definition....3937 Historical Background....3937 Scientific Fundamentals....3938 Suffix Trees....3938 Indexes....3940 Key Applications....3940 Cross-References....3940 Recommended Reading....3940 Summarizability....3941 Synonyms....3941 Definition....3941 Historical Background....3942 Foundations....3942 Notation....3942 The “Disjointness” Condition....3942 The “Completeness” Condition....3943 The “Measure Type” Condition....3943 Summary....3944 Key Applications....3944 Future Directions....3945 Cross-References....3945 Recommended Reading....3945 Summarization....3945 Synonyms....3945 Definition....3945 Historical Background....3946 Foundations....3946 Summarization Factors....3946 Processing Model....3947 Overview of Selected Techniques....3949 Additional Readings....3950 Key Applications....3950 Future Directions....3950 Experimental Results....3951 Data Sets....3951 Cross-References....3951 Recommended Reading....3951 Support Vector Machine....3952 Synonyms....3952 Definition....3952 Historical Background....3953 Foundations....3953 Motivation....3953 Formalization....3953 Key Applications....3955 Cross-References....3955 Recommended Reading....3955 Supporting Transaction Time Databases....3955 Synonyms....3955 Definition....3956 Historical Background....3956 Foundations....3956 Implementation Approaches....3957 Layered Approach....3957 Built-In Approach....3957 Managing Versions....3957 Timestamps....3957 Storing Versions on a Page....3957 Indexing Versions....3958 Compressing Versions....3958 Dealing with Timestamps....3958 Nature of Timestamps....3958 When to Timestamp....3958 Lazy Timestamping....3958 Impact of User Requested Time....3959 Additional Uses....3959 Snapshot Isolation....3959 Online Backup....3959 Bad User Transactions....3959 Key Applications....3959 Future Directions....3960 Cross-References....3960 Recommended Reading....3960 Symbolic Representation....3960 Synonyms....3960 Definition....3960 Key Points....3961 Cross-References....3961 Recommeded Reading....3961 Symmetric Encryption....3961 Synonyms....3961 Definition....3961 Key Points....3962 Cross-References....3962 Recommended Reading....3962 Synopsis Structure....3962 Synonyms....3962 Definition....3962 Key Points....3962 Cross-References....3963 Recommeded Reading....3963 Synthetic Microdata....3963 Synonyms....3963 Definition....3963 Key Points....3963 Cross-References....3964 Recommeded Reading....3964 System R (R*) Optimizer....3964 Definition....3964 Historical Background....3964 Foundations....3965 SQL Query Processing....3965 Relational Storage System....3965 Access Path Selection for Single Relations....3966 Access Path Selection for Joins....3967 R* Optimizer....3969 Key Applications....3970 Cross-References....3970 Recommended Reading....3970 T....3971 Table....3971 Synonyms....3971 Definition....3971 Key Points....3971 Cross-References....3972 Recommended Reading....3972 Tabular Data....3972 Synonyms....3972 Definition....3972 Key Points....3972 Cross-References....3972 Taxonomy: Biomedical Health Informatics....3972 Synonyms....3972 Definition....3973 Foundations....3973 Key Applications....3974 Cross-References....3975 Recommended Reading....3975 tBench....3975 Synonyms....3975 Definition....3976 Historical Background....3976 Scientific Fundamentals....3976 The DC/SD XBench Benchmark....3976 The τXBench Benchmark....3978 The PSM and PSM-DB2 Benchmarks....3979 The τPSM and Related Benchmarks....3979 The τXSchema Benchmark....3980 Supporting Tools....3981 Key Applications....3981 Future Directions....3981 URL to Code....3982 Cross-References....3982 Recommended Reading....3982 Telic Distinction in Temporal Databases....3982 Synonyms....3982 Definition....3982 Historical Background....3983 Scientific Fundamentals....3983 Data Semantics....3983 Example....3984 Query Semantics....3985 Queries About Atelic Data....3985 Queries About Telic Data....3985 Queries Combining Telic and Atelic Data....3986 Key Applications....3986 Cross-References....3986 Recommended Reading....3986 Telos....3987 Definition....3987 Historical Background....3987 Foundations....3987 Propositions....3987 Organizing Propositions....3988 Interacting with Telos Knowledge Bases....3989 Metaclasses....3990 Integrity Constraints and Deductive Rules....3991 Language Extensibility Through Metaclasses and Integrity Constraints....3991 Query Languages for Telos....3991 Temporal Knowledge in Telos....3991 Telos and RDF....3992 Key Applications....3992 URL to Code....3992 Cross-References....3992 Recommended Reading....3992 Temporal Access Control....3992 Synonyms....3992 Definition....3993 Historical Background....3993 Foundations....3994 TAM: Temporal Authorization Model....3994 TDAM: Temporal and Derived Data Authorization Model....3994 TRBAC: Temporal Role Based Access Control Model....3995 GTRBAC: Generalized Temporal Role Based Access Control Model....3995 Key Applications....3996 Future Directions....3996 Cross-References....3996 Recommended Reading....3997 Temporal Aggregation....3997 Definition....3997 Historical Background....3997 Foundations....3998 Defining Temporal Aggregation....3998 Temporal Aggregation Processing Techniques....4000 Two Scans....4000 Aggregation Tree....4000 Balanced Tree....4000 SB-Tree....4001 MVSB-Tree....4001 MDTA....4001 Key Applications....4002 Future Directions....4002 Cross-References....4002 Recommended Reading....4002 Temporal Algebras....4003 Synonyms....4003 Definition....4003 Historical Background....4003 Foundations....4003 Temporal Algebra Basics....4003 Algebras for Tuple Time-stamping....4004 Algebras for Attribute Time-stamping....4005 Valid-Time and Transaction-Time Algebras....4005 Bitemporal Relational Algebras....4005 Key Applications....4006 Cross-References....4006 Recommended Reading....4006 Temporal Analytics in Social Media....4007 Synonyms....4007 Definition....4007 Historical Background....4007 Foundations....4008 Key Applications....4008 Trend Detection....4008 User Opinion Evolution....4009 Recommended Reading....4009 Temporal Benchmarks....4010 Definition....4010 Historical Background....4011 Benchmarks....4011 Benchmark Families....4011 Benchmark Frameworks....4011 Scientific Fundamentals....4012 The Temporal SQL Benchmark....4012 The TPC-BiH Benchmark....4012 The τBench Benchmark Framework....4013 Key Applications....4014 Cross-References....4014 Recommended Reading....4014 Temporal Coalescing....4015 Definition....4015 Historical Background....4015 Foundations....4016 Implementing Temporal Coalescing ....4017 Key Applications....4018 Cross-References....4018 Recommended Reading....4018 Temporal Compatibility....4019 Definition....4019 Historical Background....4019 Scientific Fundamentals....4019 Motivation....4019 Upward Compatibility....4020 Temporal Upward Compatibility....4021 Snapshot Reducibility....4021 Sequenced Semantics....4022 Key Applications....4023 Future Directions....4023 Cross-References....4023 Recommended Reading....4023 Temporal Conceptual Models....4024 Definition....4024 Historical Background....4024 Foundations....4024 Motivating Example....4024 Syntactics....4026 Semantics....4026 Pragmatics....4026 Internal Representation....4027 Snapshot Reducibility....4027 Upward Compatibility....4027 Summary....4027 Key Applications....4028 Future Directions....4028 Experimental Results....4029 Cross-References....4029 Recommended Reading....4029 Temporal Constraints....4029 Definition....4029 Historical Background....4030 Foundations....4030 Conjunctions of Constraints....4032 Labeled Directed Graphs....4032 Difference Bound Matrices....4032 Temporal Constraints on Time Intervals....4032 Key Applications....4032 Future Directions....4033 Cross-References....4033 Recommended Reading....4033 Temporal Data Mining....4033 Synonyms....4033 Definition....4033 Historical Background....4034 Foundations....4034 Classification and Clustering....4034 Prediction....4034 Association Analysis and Extraction of Sequence Patterns....4035 Temporal, Cyclic, and Calendric Association Rules....4036 Key Applications....4037 Weather Forecasting....4037 Market Basket Analysis....4037 Stock Market Prediction....4037 Web Data Mining....4037 Cross-References....4038 Recommended Reading....4038 Temporal Data Models....4038 Synonyms....4038 Definition....4038 Historical Background....4038 Foundations....4039 Levels of Abstraction....4039 Temporal Aspects of Data....4039 Representation of Time....4040 Data Model Objects....4040 Query Languages....4042 Key Applications....4043 Future Directions....4043 Cross-References....4043 Recommended Reading....4043 Temporal Database....4043 Synonyms....4043 Definition....4043 Historical Background....4044 Foundations....4044 General Concepts....4044 Temporal Data Models....4044 Temporal Query Languages....4045 Temporal Applications....4045 Key Applications....4045 Future Directions....4046 Cross-References....4046 Recommended Reading....4046 Temporal Datawarehousing....4047 Definition....4047 Historical Background....4047 Scientific Fundamentals....4048 Slowly Changing Dimensions....4048 Temporal Databases....4049 Temporal Data Warehouses....4049 Temporal Hierarchies....4050 Temporal Facts....4051 Temporal Measures....4051 Key Applications....4052 Future Directions....4052 Cross-References....4052 Recommended Reading....4052 Temporal Dependencies....4053 Definition....4053 Historical Background....4053 Foundations....4053 Functional Dependencies Over Temporal Databases....4053 Definition....4053 Vianu's Dynamic Functional Dependency....4054 Definition....4054 Temporal Extensions of Functional Dependency Proposed by Wijsen....4054 Definition....4055 Definition....4055 Wang et al.'s Temporal Functional Dependency....4055 Definition....4056 Definition....4056 Definition....4056 Constraint-Generating Dependencies....4056 Dynamic Algebraic Dependencies....4058 Definition....4058 Key Applications....4058 Cross-References....4059 Recommended Reading....4059 Temporal Element....4060 Synonyms....4060 Definition....4060 Key Points....4060 Cross-References....4060 Recommended Reading....4060 Temporal Expression....4060 Definition....4060 Key Points....4061 Cross-References....4061 Recommended Reading....4061 Temporal Extensions in the SQL Standard....4061 Definition....4061 Historical Background....4061 Foundations....4061 Period Definitions....4062 Application-Time Period Tables....4062 Constraints on Application-Time Period Tables....4063 Querying Application-Time Period Tables....4064 System-Versioned Tables....4064 Constraints on System-Versioned Tables....4066 Querying System-Versioned Tables....4066 Bitemporal Tables....4066 Cross-References....4067 Recommended Reading....4067 Temporal Generalization....4067 Definition....4067 Key Points....4067 Cross-References....4068 Recommended Reading....4068 Temporal Granularity....4068 Synonyms....4068 Definition....4068 Historical Background....4069 Foundations....4069 Definitions....4069 Granularity Relationships....4070 Defining New Granularities Through Algebraic Operators....4071 Key Applications....4072 Experimental Results....4073 Cross-References....4073 Recommended Reading....4073 Temporal Homogeneity....4073 Definition....4073 Key Points....4074 Cross-References....4074 Recommended Reading....4074 Temporal Indeterminacy....4074 Synonyms....4074 Definition....4074 Historical Background....4075 Foundations....4075 Key Applications....4077 Cross-References....4077 Recommended Reading....4077 Temporal Integrity Constraints....4078 Synonyms....4078 Definition....4078 Historical Background....4078 Foundations....4078 Defining Temporal Integrity....4078 Temporal, Transition, and Static Constraints....4078 Different Notions of Consistency....4080 Expressiveness of Temporal Constraints....4081 Constraints on Interval-Stamped Temporal Data....4081 Checking and Enforcing Temporal Integrity....4082 Key Applications....4084 Cross-References....4084 Recommended Reading....4084 Temporal Joins....4084 Definition....4084 Historical Background....4085 Scientific Fundamentals....4085 Cartesian Product....4086 Theta-Join....4086 Equijoin....4086 Natural Join....4086 Outer Joins and Outer Cartesian Products....4087 Reducibility....4089 Evaluation Algorithms....4089 Key Applications....4090 Cross-References....4090 Recommended Reading....4090 Temporal Logic in Database Query Languages....4090 Definition....4090 Historical Background....4091 Foundations....4091 Extensions....4092 Expressive Power....4094 Key Applications....4095 Cross-References....4095 Recommended Reading....4095 Temporal Logical Models....4096 Synonyms....4096 Definition....4096 Historical Background....4096 Foundations....4096 The Treatment of Time in Database Systems....4096 Temporal Data Behavior....4096 Behavioral Properties of Temporal Sequences....4099 Operation over Temporal Data....4100 Predicate Operators over Time Sequences....4100 Aggregation Operators over Time Windows....4101 Aggregation Operators over Time Sequence Collections....4101 Composition of Time Sequences....4101 Combinations of the Above Operators....4101 Additional Concepts....4101 Key Applications....4102 Future Directions....4102 Cross-References....4102 Recommended Reading....4102 Temporal Object-Oriented Databases....4103 Definition....4103 Historical Background....4103 Scientific Fundamentals....4103 Time and Abstract Data Types....4104 Temporal Object Data Models....4105 General OO Models Using OO Concepts for Modeling Temporal Dimensions....4106 OO Models Having Explicit Constructs for Temporal Dimensions of Data....4107 Temporal Object Query Languages....4108 Temporal Object-Oriented Database Systems....4108 Key Applications....4108 Future Directions....4109 Cross-References....4109 Recommended Reading....4109 Temporal Periodicity....4110 Synonyms....4110 Definition....4110 Historical Background....4110 Sccientific Fundamentals....4110 Deductive Rule-Based Approaches....4111 Constraint-Based Approaches....4111 Symbolic Approaches....4112 Key Applications....4113 Cross-References....4114 Recommended Reading....4114 Temporal Projection....4114 Synonyms....4114 Definition....4114 Key Points....4115 Cross-References....4115 Recommended Reading....4115 Temporal PSM....4115 Synonyms....4115 Definition....4115 Historical Background....4115 Scientific Fundamentals....4116 Overview of Temporal SQL....4116 Temporal SQL/PSM....4118 Implementation....4119 Summary....4120 Key Applications....4121 Temporal Stored Modules....4121 Cross-References....4121 Recommended Reading....4121 Temporal Query Languages....4121 Synonyms....4121 Definition....4121 Historical Background....4121 Scientific Fundamentals....4122 Language Extension Approaches....4122 Abstract Data Types for Time....4122 Use of Point Timestamps....4123 Syntactical Defaults....4123 Semantic Defaults....4124 Additional Characterizations of Temporal Query Languages....4124 Support for Temporal Queries in Existing DBMSes....4125 Key Applications....4125 Cross-References....4125 Recommended Reading....4126 Temporal Query Processing....4126 Definition....4126 Historical Background....4126 Foundations....4127 Functionalities....4127 The Layered Architecture....4127 The Monolithic Architecture....4128 The Extensible Architecture....4128 Key Applications....4129 Future Directions....4129 Cross-References....4129 Recommended Reading....4129 Temporal Relational Calculus....4130 Synonyms....4130 Definition....4130 Key Points....4130 Cross-References....4131 Recommended Reading....4131 Temporal Specialization....4131 Synonyms....4131 Definition....4132 Key Points....4132 Cross-References....4133 Recommended Reading....4133 Temporal Strata....4133 Synonyms....4133 Definition....4133 Historical Background....4134 Scientific Fundamentals....4134 Key Applications....4138 Future Directions....4138 Cross-References....4138 Recommended Reading....4138 Temporal Vacuuming....4138 Synonyms....4138 Definition....4138 Historical Background....4138 Foundations....4139 Formal Vacuuming Specifications....4139 Space/Storage Requirements....4140 Approaches to Vacuuming....4141 Administrative Approaches to Vacuuming....4141 Application/Query-Driven Approaches....4142 Key Applications....4142 Future Directions....4142 Cross-References....4143 Recommended Reading....4143 Temporal Visual Languages....4143 Synonyms....4143 Definition....4143 Historical Background....4144 Foundations....4144 Key Applications....4148 Cross-References....4149 Recommended Reading....4149 Temporal XML....4149 Synonyms....4149 Definition....4149 Historical Background....4150 Scientific Fundamentals....4150 Key Applications....4151 Future Directions....4152 Cross-References....4152 Recommended Reading....4152 Term Proximity....4153 Synonyms....4153 Definition....4153 Key Points....4153 Cross-References....4153 Recommended Reading....4153 Term Statistics for Structured Text Retrieval....4153 Synonyms....4153 Definition....4154 Key Points....4154 Cross-References....4154 Recommended Reading....4154 Term Weighting....4155 Definition....4155 Historical Background....4155 Foundations....4156 Term Frequency....4156 Inverse Document Frequency....4156 Document Length....4156 Term Weighting Schemes....4157 TF*IDF....4157 BM25 (OKAPI Retrieval Function)....4157 Language Modeling....4157 Key Applications....4157 Experimental Results....4157 Cross-References....4158 Recommended Reading....4158 Test Collection....4158 Synonyms....4158 Definition....4158 Key Points....4159 Cross-References....4159 Recommended Reading....4159 Text Analytics....4159 Cross-References....4159 Text Analytics in Social Media....4159 Synonyms....4159 Definition....4159 Historical Background....4159 Foundations....4160 Key Applications....4160 Future Directions....4161 Recommended Reading....4161 Text Categorization....4161 Synonyms....4161 Definition....4162 Historical Background....4162 Foundations....4162 Document Representation....4162 Dimensionality Reduction....4163 Classification Algorithms....4163 Naïve Bayesian Classifier (NB)....4163 Support Vector Machine (SVM)....4164 Performance Measures....4164 Key Applications....4164 Data Sets....4164 Cross-References....4164 Recommended Reading....4165 Text Clustering....4165 Definition....4165 Historical Background....4165 Foundations....4165 Document Representation....4165 Text Clustering Algorithms....4166 Single-Link Clustering....4166 K-Means Clustering....4166 Co-clustering....4167 Performance Measurements....4167 Internal Quality Measure....4167 External Quality Measure....4167 Key Applications....4168 Cross-References....4168 Recommended Reading....4168 Text Compression....4168 Synonyms....4168 Definition....4168 Key Points....4168 Cross-References....4170 Recommended Reading....4170 Text Generation....4171 Synonyms....4171 Definition....4171 Historical Background....4171 Foundations....4171 Text Generation System Architecture....4171 Input and Output....4171 Architectures....4171 Key Applications....4172 Cross-References....4173 Recommended Reading....4173 Text Index Compression....4173 Synonyms....4173 Definition....4173 Historical Background....4173 Scientific Fundamentals....4174 Inverted Index Compression....4175 Full-Text Searching....4176 Relevance Ranking....4176 Key Applications....4177 Future Directions....4177 Experimental Results....4178 Url to Code....4178 Recommended Reading....4178 Text Indexing and Retrieval....4179 Synonyms....4179 Definition....4179 Historical Background....4179 Foundations....4180 Key Applications....4182 Future Directions....4182 Data Sets....4182 Cross-References....4182 Recommended Reading....4182 Text Indexing Techniques....4182 Definition....4182 Historical Background....4182 Foundations....4183 Key Applications....4185 Cross-References....4185 Recommended Reading....4185 Text Mining....4186 Synonyms....4186 Definition....4186 Historical Background....4186 Foundations....4186 Text Classification....4187 Text Clustering....4187 Information Extraction....4188 Document Summarization....4188 Key Phrase Extraction....4188 Topic Detection and Tracking (TDT)....4188 Opinion Mining....4189 Key Applications....4189 Bioinformatics....4189 Email Spam Filtering....4189 Business Intelligence....4189 URL to Code....4189 Cross-References....4189 Recommended Reading....4190 Text Mining of Biological Resources....4190 Synonyms....4190 Definition....4190 Historical Background....4191 Foundations....4191 Resources....4191 Methods....4192 Key Applications....4193 Future Directions....4193 Cross-References....4194 Recommended Reading....4194 Text Representation....4194 Definition....4194 Historical Background....4194 Foundations....4195 Key Applications....4197 Future Directions....4197 Data Sets....4197 Cross-References....4198 Recommended Reading....4198 Text Segmentation....4198 Synonyms....4198 Definition....4198 Historical Background....4198 Foundations....4200 Key Applications....4201 Future Directions....4201 Data Sets....4201 Cross-References....4201 Recommended Reading....4202 Text Semantic Representation....4202 Definition....4202 Historical Background....4202 Foundations....4203 Key Applications....4204 Future Directions....4205 Data Sets....4205 Cross-References....4205 Recommended Reading....4205 Text Stream Processing....4205 Synonyms....4205 Definition....4205 Historical Background....4206 Scientific Fundamentals....4206 Categorization/Classification....4206 Clustering....4207 Topic Monitoring....4207 Bursty Event Detection....4207 Pattern Matching....4208 Key Applications....4208 Future Directions....4209 Data Sets....4209 Cross-References....4209 Recommended Reading....4209 Text Streaming Model....4209 Definition....4209 Historical Background....4210 Foundations....4210 Key Applications....4211 Data Sets....4211 Recommended Reading....4211 Text Summarization....4211 Synonyms....4211 Definition....4211 Historical Background....4211 Foundations....4211 Extractive Summarization Algorithms....4212 Unsupervised Methods....4212 Supervised Methods....4213 Evaluation....4214 Key Applications....4214 Data Sets....4214 Cross-References....4215 Recommended Reading....4215 Text Visualization....4215 Synonyms....4215 Definition....4215 Historical Background....4215 Foundations....4216 Key Applications....4217 Future Directions....4217 Cross-References....4218 Recommended Reading....4218 TF*IDF....4218 Synonyms....4218 Definition....4218 Key Points....4218 Cross-References....4219 Recommended Reading....4219 Thematic Map....4219 Synonyms....4219 Definition....4219 Key Points....4220 Cross-References....4220 Recommended Reading....4220 Third Normal Form....4220 Synonyms....4220 Definition....4221 Key Points....4221 Cross-References....4221 Recommended Reading....4221 Three-Dimensional GIS and Geological Applications....4221 Synonyms....4221 Definition....4221 Historical Background....4222 Foundations....4222 Key Applications....4223 Cross-References....4224 Recommended Reading....4224 Three-Phase Commit....4225 Definition....4225 Historical Background....4225 Foundations....4225 Dynamics of Three-Phase Commit....4225 Recovery in Three-Phase Commit....4226 Non-blocking Commit Protocol Variants....4227 Other Atomic Commit Protocol Variants and Optimizations....4227 Key Applications....4230 Cross-References....4230 Recommended Reading....4231 Tight Coupling....4231 Synonyms....4231 Definition....4231 Key Points....4231 Cross-References....4231 Time Aggregated Graphs....4231 Synonyms....4231 Definition....4232 Key Points....4232 Recommended Reading....4232 Time and Information Retrieval....4232 Synonyms....4232 Definition....4232 Historical Background....4232 Scientific Fundamentals....4233 Overview and Motivation....4233 Time and Timelines....4233 Temporal Expressions....4234 Temporal Processing Pipeline....4235 Document Retrieval....4235 Key Applications....4236 Timeline-Based Exploration....4236 Social Media Organization....4236 Archives....4236 Spatiotemporal Exploration....4236 Future Directions....4237 Cross-References....4237 Recommended Reading....4237 Time Domain....4237 Synonyms....4237 Definition....4237 Historical Background....4238 Foundations....4238 Basics....4238 Temporal Models and Query Languages....4239 Time Domain and Granularity....4239 The Association of Time with Data....4240 Key Applications....4240 Future Directions....4241 Cross-References....4241 Recommended Reading....4241 Time in Philosophical Logic....4242 Synonyms....4242 Definition....4242 Historical Background....4242 Foundations....4243 Dynamical and Static Time: A-Theory Versus B-Theory....4243 Linear versus Branching Time....4244 Punctual Versus Durational Time....4244 Definition ....4245 Time and Narratives....4246 Key Applications....4246 Cross-References....4246 Recommended Reading....4247 Time Instant....4247 Synonyms....4247 Definition....4247 Key Points....4247 Cross-References....4248 Recommended Reading....4248 Time Interval....4248 Synonyms....4248 Definition....4248 Key Points....4248 Cross-References....4248 Recommended Reading....4249 Time Period....4249 Synonyms ....4249 Definition....4249 Key Points....4249 Cross-References....4249 Time Series Query....4249 Synonyms....4249 Definition....4249 Historical Background....4250 Foundations....4250 Basic Concepts....4250 Time Series Query....4251 Query Processing: Index-Based Methods for Similarity Search....4252 Query Processing: Similarity Search over Streaming Time Series....4253 Key Applications....4254 Data Sets....4254 URL to Code....4254 Cross-References....4254 Recommended Reading....4255 Time Span....4255 Synonyms....4255 Definition....4255 Key Points....4256 Cross-References....4256 Recommended Reading....4256 Time-Line Clock....4256 Synonyms....4256 Definition....4256 Key Points....4256 Cross-References....4256 Recommended Reading....4256 Timeslice Operator....4257 Synonyms....4257 Definition....4257 Key Points....4257 Cross-References....4257 Recommended Reading....4257 Topic Detection and Tracking....4257 Definition....4257 Historical Background....4258 Foundations....4258 The Segmentation Task....4258 The Detection Task....4259 Retrospective Event Detection....4259 Online New Event Detection....4259 The Tracking Task....4259 Key Applications....4260 Future Directions....4260 Data Sets....4260 Recommended Reading....4260 Topic Maps....4261 Definition....4261 Historical Background....4261 Foundations....4261 Using Topic Maps....4261 The Basics of Topic Maps....4261 Extending the Basic Model....4263 Merging Topic Maps....4263 Using Topic Maps....4263 Key Applications....4263 Cross-References....4263 Recommended Reading....4263 Topic-Based Publish/Subscribe....4263 Synonyms....4263 Definition....4264 Key Points....4264 Cross-References....4266 Recommended Reading....4266 Top-k Queries....4266 Synonyms....4266 Definition....4266 Key Applications....4267 Cross-References....4267 Top-K Selection Queries on Multimedia Datasets....4267 Synonyms....4267 Definition....4267 Historical Background....4267 Foundations....4268 Query Model....4268 Top-k Query Evaluation Algorithms....4268 The Threshold Algorithm....4269 Algorithms Based on Expensive Predicates Evaluation....4269 Filter/Restart Method....4269 Using Pre-computed Views....4270 Handling Joins....4270 Key Applications....4270 Multimedia Search....4270 Information Integration....4270 Future Directions....4270 Cross-References....4270 Recommended Reading....4270 Topological Data Models....4271 Synonyms....4271 Definition....4271 Historical Background....4271 Foundations....4272 DIME Files....4273 POLYVRT....4274 GIRAS....4274 TIGER....4275 ARC/INFO Coverages....4276 Relational....4277 ArcGIS Geodatabase....4277 Key Applications....4279 Cross-References....4279 Recommended Reading....4279 Topological Relationships....4280 Definition....4280 Historical Background....4280 Foundations....4280 Topological Relationships for Simple Objects....4280 Topological Relationships for Complex Objects....4281 Topological Relationships for Objects with Vague Boundary....4281 Key Applications....4281 Geographic Information Systems (GISs)....4281 Qualitative Spatial Reasoning (QSR)....4281 Geospatial Semantic Web (GSW)....4281 Future Directions....4282 Experimental Results....4282 Cross-References....4283 Recommended Reading....4283 Trajectory....4283 Synonyms....4283 Definition....4283 Key Points....4284 Cross-References....4284 References....4284 Transaction....4284 Synonyms....4284 Definition....4284 Key Points....4284 Cross-References....4285 Recommended Reading....4285 Transaction Chopping....4285 Definition....4285 Key Points....4285 Assumptions....4286 Basic Definitions....4286 Correct Choppings....4286 Conclusion....4287 Recommended Reading....4287 Transaction Management....4287 Synonyms....4287 Definition....4287 Historical Background....4287 Foundations....4287 Key Applications....4290 Future Directions....4291 Experimental Results....4291 Cross-References....4291 Recommended Readings....4291 Transaction Manager....4292 Definition....4292 Key Points....4292 Cross-References....4292 Recommended Reading....4292 Transaction Models: The Read/Write Approach....4292 Synonyms....4292 Definition....4293 Historical Background....4293 Foundations....4293 Definition of a Transaction....4293 Schedules and Histories....4294 Schedule Correctness....4295 Commutativity of Operations....4295 Key Applications....4296 Future Directions....4297 Experimental Results....4297 Cross-References....4297 Recommended Reading....4297 Transaction Time....4298 Synonyms....4298 Definition....4298 Main Text....4298 Cross-References....4299 Recommended Reading....4299 Transactional Middleware....4299 Synonyms....4299 Definition....4299 Historical Background....4300 Foundations....4300 Key Applications....4301 Future Directions....4302 Cross-References....4302 Recommended Reading....4302 Transactional Processes....4302 Synonyms....4302 Definition....4302 Key Points....4302 Cross-References....4303 Recommended Reading....4303 Transactional Stream Processing....4303 Synonyms....4303 Definition....4303 Historical Background....4303 Scientific Fundamentals....4304 Correctness Guarantees....4304 Techniques....4305 Key Applications....4308 Future Directions....4308 Cross-References....4308 Recommended Reading....4309 Transaction-Time Indexing....4309 Synonyms....4309 Definition....4309 Historical Background....4309 Foundations....4310 Key Applications....4314 Cross-References....4314 Recommended Reading....4314 Tree-Based Indexing....4315 Synonyms....4315 Definition....4315 Key Points....4315 Cross-References....4316 Recommended Reading....4316 Treemaps....4316 Definition....4316 Historical Background....4317 Foundations ....4318 Key Applications....4320 Cross-References....4320 Recommended Reading....4321 Triangular Norms....4321 Synonyms....4321 Definition....4321 Key Points....4321 Cross-References....4322 Recommended Reading....4322 Triangulated Irregular Network....4322 Synonyms....4322 Definition....4322 Key Points....4322 Cross-References....4323 Recommended Reading....4323 Trie....4323 Synonyms....4323 Definition....4323 Historical Background....4323 Scientific Fundamentals....4324 Construction....4324 Searching....4324 Sorting....4325 Implementation....4325 Compact Tries....4325 PATRICIA Trees....4326 Key Applications....4326 Cross-References....4326 Recommended Reading....4326 Trip Planning Queries....4327 Synonyms....4327 Definition....4327 Historical Background....4328 Scientific Fundamentals....4329 Key Applications....4331 Geographic Information Systems (GIS)....4331 Location-Based Services (LBS)....4331 Tourism Recommender Systems....4331 Future Directions....4331 Experimental Results....4332 Cross-References....4332 Recommended Reading....4332 Trust and Reputation in Peer-to-Peer Systems....4333 Synonyms....4333 Definition....4333 Historical Background....4333 Foundations....4334 Key Applications....4338 Cross-References....4338 Recommended Reading....4338 Trust in Blogosphere....4338 Synonyms....4338 Definition....4338 Historical Background....4339 Scientific Fundamentals....4341 Key Applications....4341 Future Directions....4342 Datasets....4342 Cross-References....4342 Recommended Reading....4342 Trusted Hardware....4343 Synonyms....4343 Definition....4343 Key Points....4343 Cross-References....4343 Recommended Reading....4344 TSQL2....4344 Definition....4344 Historical Background....4344 Foundations....4345 Design Goal for TSQL2....4345 Language Concepts in TSQL2....4346 Time Ontology....4346 Baseline Clock....4347 Data Types....4347 Time-Lines....4347 Aggregates....4347 Valid-Time Tables....4347 Transaction-Time and Bitemporal Tables....4348 Schema Specification....4348 Restructuring....4348 Temporal Selection....4348 Temporal Projection....4349 Update....4349 Cursors....4349 Schema Versioning....4349 Vacuuming....4349 System Tables....4349 SQL-92 Compatibility....4349 Implementation....4349 Key Applications....4349 Future Directions....4349 URL to Code....4350 Cross-References....4350 Recommended Reading....4350 Tuning Concurrency Control....4350 Synonyms....4350 Definition....4350 Historical Background....4351 Foundations....4351 Leveraging Application Semantics....4351 Living Dangerously....4351 General Rules of Thumb....4352 Key Applications....4352 Experimental Results....4352 Value of Serializability....4352 Counters....4353 URL to Code and Data Sets....4354 Cross-References....4354 Recommended Reading....4354 Tuple-Generating Dependencies....4354 Synonyms....4354 Definition....4354 Key Points....4354 Cross-References....4355 Recommended Reading....4355 Two-Dimensional Shape Retrieval....4355 Definition....4355 Historical Background....4355 Foundations....4355 Key Applications....4356 Content Based Image Retrieval....4356 Visual Surveillance....4357 Future Directions....4357 Cross-References....4357 Recommended Reading....4357 Two-Phase Commit....4357 Definition....4357 Historical Background....4357 Scientific Fundamentals....4357 Dynamics of Two-Phase Commit....4358 Recovery in Two-Phase Commit....4359 Underlying Assumptions....4360 Performance Issues....4360 Most Common Two-Phase Commit Variants....4361 Compatibility of 2PC Variants....4362 Key Applications....4363 Cross-References....4363 Recommended Reading....4363 Two-Phase Commit Protocol....4364 Synonyms....4364 Definition....4364 Historical Background....4364 Foundations....4364 Basic Protocol....4364 Protocol Restart....4366 Hierarchical and Flattened 2PC....4366 Optimizations....4367 Key Applications....4368 Cross-References....4368 Recommended Reading....4368 Two-Phase Locking....4368 Synonyms....4368 Definition....4369 Historical Background....4369 Foundations....4369 Key Applications....4373 Cross-References....4373 Recommended Reading....4373 Two-Poisson Model....4373 Synonyms....4373 Definition....4373 Historical Background....4374 Foundations....4374 Key Applications....4375 Cross-References....4375 Recommended Reading....4375 Type-Based Publish/Subscribe....4375 Definition....4375 Key Points....4376 Cross-References....4376 Recommended Reading....4376 U....4377 U-Measure....4377 Definition....4377 Main Text....4377 Cross-References....4378 Uncertain Data Lineage....4378 Synonyms....4378 Definition....4378 Historical Background....4378 Scientific Fundamentals....4379 Key Applications....4383 Cross-References....4383 Recommended Reading....4383 Uncertain Data Mining....4384 Synonyms....4384 Definition....4385 Historical Background....4385 Scientific Fundamentals....4386 Data Uncertainty....4386 Data Mining Tasks....4387 Cluster Analysis....4387 Classification....4389 Frequent Pattern Mining....4391 Cross-References....4393 Recommended Reading....4393 Uncertain Data Models....4395 Synomyms....4395 Definition....4395 Scientific Fundamentals....4395 Basic Terminology and Possible Worlds Semantics....4395 Expressive Power of Representation Systems....4395 Conditional Tables....4396 Probabilistic c-Tables and Graphical Models....4397 From Weaker Representation Systems to Lineage....4398 Key Applications....4399 Cross-References....4399 Recommended Reading....4400 Uncertain Data Streams....4400 Synonyms....4400 Definition....4400 Historical Background....4400 Scientific Fundamentals....4401 Data Model for Uncertain Data Streams....4401 Query Semantics over Uncertain Data Streams....4402 Query Evaluation Methodology....4403 Key Applications....4404 Cross-References....4405 Recommended Reading....4405 Uncertain Graph Data Management....4405 Synonyms....4405 Definition....4406 Historical Background....4406 Scientific Fundamentals....4406 Uncertain Graph Data Modeling....4406 Possible World and Reliability....4407 Graph Indexing and Query Processing....4408 Connectivity Query....4408 k-Nearest Neighbors' Query....4409 Most Reliable Subgraph Query....4410 Subgraph Matching Query....4410 Key Applications....4411 Reliable System Design....4411 Social Network Analysis....4411 Biomedical Study....4411 Cross-References....4411 Recommended Reading....4411 Uncertain Spatial Data Management....4412 Synonyms....4412 Definition....4412 Historical Background....4412 Foundations....4412 Key Applications....4415 Future Directions....4416 URL to Code....4416 Cross-References....4416 Recommended Reading....4416 Uncertain Top-k Queries....4417 Synonyms....4417 Definition....4417 Historical Background....4417 Scientific Fundamentals....4418 Key Applications....4420 Cross-References....4420 Recommended Reading....4420 Uncertainty in Events....4421 Synonyms....4421 Definition....4421 Historical Background....4421 Foundations....4421 Dimensions of Event Uncertainty....4422 Causes of Event Uncertainty....4423 Handling Uncertainty in Events....4424 Example of Event Uncertainty Handling Framework....4424 Key Applications....4425 Future Directions....4425 Cross-References....4426 Recommended Reading....4426 Uncertainty Management in Scientific Database Systems....4426 Definition....4426 Historical Background....4426 Foundations....4427 Uncertainties in Scientific Data....4427 General Purpose Systems for Managing Uncertainty....4427 Trio....4427 MystiQ....4428 Other Systems....4428 The UII System for Managing Uncertainty in Scientific Data....4428 Handling Uncertainty....4429 Uncertainty Metrics....4429 Probabilistic Query Evaluation....4431 Key Applications....4431 Future Directions....4431 Cross-References....4432 Recommended Reading....4432 Unicode....4433 Definition....4433 Key Points....4433 Cross-References....4433 Unified Modeling Language....4433 Synonyms....4433 Definition....4433 Historical Background....4433 Foundations....4434 UML Class and Object Diagrams....4434 UML Class Diagram Features for Conceptual Schemas....4436 Key Applications....4441 Cross-References....4441 Recommended Reading....4441 Union....4442 Definition....4442 Key Points....4442 Cross-References....4442 Unobservability....4442 Synonyms....4442 Definition....4442 Key Points....4442 Cross-References....4442 Recommended Reading....4443 Updates and Transactions in Peer-to-Peer Systems....4443 Synonyms....4443 Definition....4443 Historical Background....4443 Foundations....4443 Single-Owner/Primary Copy....4444 Owner-Resolver....4444 Consensus....4445 Partial Divergence....4445 Key Applications....4446 Future Directions....4446 Cross-References....4446 Recommended Reading....4446 Updates Through Views....4447 Definition....4447 Historical Background....4447 Foundations....4447 Key Applications....4450 Cross-References....4450 Recommended Reading....4450 Usability....4451 Synonyms....4451 Definition....4451 Historical Background....4451 Foundations....4451 Software Usability....4452 Data Usability....4452 Key Applications....4452 User Centered Design....4452 Context of Use....4453 User and Organizational Requirements....4453 Design Solutions....4453 Usability Evaluation....4453 When to Use Methods for Design Feedback....4454 When to Use Validation Methods....4454 Validity....4454 Cost Benefits....4454 Usability of Digital Libraries....4455 Cross-References....4455 Recommended Reading....4455 User-Defined Time....4455 Definition....4455 Key Points....4456 Cross-References....4456 Recommended Reading....4456 V....4457 Valid Time....4457 Synonyms....4457 Definition....4457 Main Text....4457 Cross-References....4458 Recommended Reading....4458 Valid-Time Indexing....4458 Synonyms....4458 Definition....4458 Historical Background....4458 Foundations....4459 Key Applications....4462 Cross-References....4463 Recommended Reading....4463 Value Equivalence....4463 Definition....4463 Main Text....4464 Cross-References....4464 Variable Time Span....4464 Synonyms....4464 Definition....4464 Key Points....4464 Cross-References....4464 Recommended Reading....4464 Vector-Space Model....4464 Synonyms....4464 Definition....4464 Historical Background....4465 Foundations....4465 Basic Definitions....4465 Mathematical Development....4466 Rationale....4468 Key Applications....4469 Future Directions....4469 Cross-References....4469 Recommended Reading....4469 Vertically Partitioned Data....4470 Synonyms....4470 Definition....4470 Key Points....4470 Cross-References....4472 Recommended Reading....4472 Video....4472 Synonyms....4472 Definition....4472 Historical Background....4472 Scientific Fundamentals....4473 Video Generation....4473 Video Representation....4473 Video Content Analysis....4474 Visual Content Analysis....4474 Audio Content Analysis....4475 Audiovisual Content Analysis....4475 Video Application....4476 Video Indexing and Browsing....4476 Video Abstraction....4476 Content-Based Video Retrieval....4477 Key Applications....4477 Cross-References....4478 Recommended Reading....4478 Video Content Analysis....4479 Synonyms....4479 Definition....4480 Historical Background....4480 Foundations....4480 Partitioning Video....4481 Audio Analysis....4482 Speech Recognition for Video Content Analysis and Retrieval....4482 Speaker and Audio Type Identification....4482 Content Analysis from Individual Image Frames....4482 Metadata Extraction Unique to Video....4482 Motion Feature Analysis....4483 Camera Motion Analysis....4483 Video OCR (VOCR)....4484 Combination of Audio Analysis, Image Analysis, and Motion Analysis for Semantic Content Analysis....4485 Key Applications....4486 Cross-References....4486 Recommended Reading....4486 Video Content Modeling....4487 Synonyms....4487 Definition....4487 Historical Background....4487 Foundations....4487 Key Applications....4490 Cross-References....4490 Recommended Reading....4490 Video Content Structure....4491 Synonyms....4491 Definition....4491 Historical Background....4492 Foundations....4492 Shot Detection....4492 Scene Grouping....4493 Story Identification....4494 Subshot Segmentation....4495 Keyframe Extraction....4495 Key Applications....4496 Future Directions....4496 Experimental Results....4496 Cross-References....4497 Recommended Reading....4497 Video Metadata....4497 Synonyms....4497 Definition....4497 Historical Background....4498 Foundations....4499 Shot Description....4499 Sequence....4502 Rights Management....4504 Key Applications....4504 Cross-References....4504 Recommended Reading....4504 Video Querying....4505 Synonyms....4505 Definition....4505 Historical Background....4505 Foundations....4506 Key Applications....4508 Future Directions....4508 Cross-References....4509 Recommended Reading....4509 Video Representation....4509 Synonyms....4509 Definition....4509 Historical Background....4509 Foundations....4510 Basics of Video Representation....4510 Video Compression....4511 Frame Types in MPEG-1....4512 Intra-frame Compression....4512 Inter-frame Compression....4513 H.264/AVC Standard....4513 Audio Compression....4514 Streaming Videos....4515 Key Applications....4516 Future Directions....4516 Cross-References....4516 Recommended Reading....4516 Video Scene and Event Detection....4517 Synonyms....4517 Definition....4517 Historical Background....4517 Foundations....4518 Key Applications....4521 Future Directions....4521 Experimental Results....4522 Data Sets....4522 Cross-References....4522 Recommended Reading....4523 Video Segmentation....4523 Synonyms....4523 Definition....4523 Historical Background....4524 Foundations....4525 Shot-Cut Detection....4525 Scene Boundary Detection....4526 Key Applications....4527 Cross-References....4528 Recommended Reading....4528 Video Sequence Indexing....4529 Synonyms....4529 Definition....4529 Historical Background....4529 Foundations....4530 Key Applications....4531 Future Directions....4531 Experimental Results....4531 Data Sets....4531 URL to Code....4531 Cross-References....4531 Recommended Reading....4532 Video Shot Detection....4532 Synonyms....4532 Definition....4532 Historical Background....4533 Foundations....4533 Cut....4533 Dissolve....4534 Wipe....4535 General Challenges....4535 Key Applications....4535 Experimental Results....4536 Data Sets....4536 Recommended Reading....4536 Video Summarization....4537 Synonyms....4537 Definition....4537 Historical Background....4537 Foundations....4537 Features for Content Analysis....4538 Importance Measure for Summary Generation....4538 Domain-Specific Video Summarization....4539 Key Applications....4540 Multimedia Archives Indexing and Retrieval....4540 Movie Marketing....4540 Home Entertainment....4540 Future Directions....4540 Performance Evaluation....4540 Comprehensive Understanding and Modeling of Video Content....4540 From Large-Scale Video Summarization to Search and Browsing....4540 Experimental Results....4540 Data Sets....4541 Rushes Videos by TRECVID Workshop.....4541 Cross-References....4541 References....4541 View Adaptation....4541 Synonyms....4541 Definition....4541 Key Points....4542 Cross-References....4542 Recommended Reading....4542 View Definition....4542 Synonyms....4542 Definition....4542 Key Points....4542 Cross-References....4543 Recommended Reading....4543 View Maintenance....4543 Synonyms....4543 Definition....4543 Historical Background....4544 Foundations....4544 View Recomputation....4544 Incremental View Maintenance....4544 Immediate View Maintenance....4545 Deferred View Maintenance....4545 Offline View Maintenance....4545 Online View Maintenance....4545 Key Applications....4545 Cross-References....4546 Recommended Reading....4546 View Maintenance Aspects....4546 Definition....4546 Historical Background....4546 Foundations....4547 Time Dimension....4547 Expressiveness of View Definition Language....4548 Available Information....4548 Supported Modifications....4548 Algorithm Applicability....4549 Key Applications....4549 Data Warehousing....4549 Data Streams....4549 Caching....4549 Mobile Applications....4549 Cross-References....4550 Recommended Reading....4550 View-Based Data Integration....4550 Definition....4550 Historical Background....4550 Foundations....4551 Specifying the Relationship of the Sources with the Unified View....4551 Global as View (GAV)....4553 Local as View (LAV)....4555 Global and Local as View (GLAV)....4557 Alternatives to VDISs....4557 Key Applications....4558 Cross-References....4558 Recommended Reading....4558 Views....4559 Synonyms....4559 Definition....4559 Key Points....4559 Cross-References....4560 Recommended Reading....4560 Virtual Partitioning....4560 Synonyms....4560 Definition....4560 Key Points....4560 Cross-References....4561 Recommended Reading....4561 Visual Analytics....4561 Synonyms....4561 Definition....4561 Historical Background....4562 Foundations....4562 Visual Analytics Process....4563 Technical and Social Challenges....4564 Key Applications....4565 Cross-References....4566 Recommended Reading....4567 Visual Association Rules....4567 Synonyms....4567 Definition....4567 Historical Background....4567 Foundations....4569 Key Applications....4572 Future Directions....4572 Cross-References....4572 Recommended Reading....4572 Visual Classification....4573 Synonyms....4573 Definition....4573 Historical Background....4573 Foundations....4573 Propose Split....4575 Look-Ahead....4575 Expand Subtree....4575 Key Applications....4576 Cross-References....4576 Recommended Reading....4576 Visual Clustering....4576 Synonyms....4576 Definition....4577 Historical Background....4577 Foundations....4577 Visual Exploration of a Given Clustering Structure....4577 Extension of an Optimized Clustering Algorithm....4578 Clustering Based on Visual User Feedback and Refinement....4580 Visualization Used as Interactive Feature Selection for Clustering....4582 Key Applications....4582 Cross-References....4582 Recommended Reading....4582 Visual Content Analysis....4583 Synonyms....4583 Definition....4583 Historical Background....4583 Foundations....4583 Key Applications....4586 Broadcasting....4586 Narrow Casting....4586 Law Enforcement....4586 Web Search....4586 Future Directions....4586 Data Sets....4586 Experimental Results....4588 Cross-References....4588 Recommended Reading....4588 Visual Data Mining....4589 Synonyms....4589 Definition....4589 Historical Background....4589 Foundations....4589 Key Applications....4591 Future Directions....4592 Experimental Results....4592 Data Sets....4592 URL to Code....4592 Visual Data Exploration and Mining....4592 Open Source....4592 Commercial....4593 General Visualization Engines and Development Tools....4593 Open Source....4593 Cross-References....4593 Recommended Reading....4593 Visual Formalisms....4594 Definition....4594 Historical Background....4594 Foundations....4595 Key Applications....4597 Software and Systems Structural Specification....4597 Reactive Systems Behavioral Specification....4597 Data Modeling and Querying....4597 Cross-References....4597 Recommended Reading....4598 Visual Interaction....4598 Synonyms....4598 Definition....4598 Historical Background....4599 Foundations....4599 Key Applications....4602 Future Directions....4602 Cross-References....4603 Recommended Reading....4603 Visual Interfaces....4604 Synonyms....4604 Definition....4604 Historical Background....4604 Foundations....4605 Key Applications....4606 Future Directions....4606 Experimental Results....4607 Cross-References....4608 Recommended Reading....4608 Visual Interfaces for Geographic Data....4608 Synonyms....4608 Definition....4608 Historical Background....4608 Scientific Fundamentals....4609 Visual Interfaces for Cartographic Output....4609 Generalities....4609 Generalization....4609 Graphic Semiology....4610 Animation....4610 Chorems....4610 Mash-Ups....4610 Query Input....4610 Geovisualization....4612 Key Applications....4613 Future Directions....4613 Visual Access to Geographic Databases....4613 Cross-References....4613 Recommended Reading....4613 Visual Metaphor....4614 Synonyms....4614 Definition....4614 Key Points....4614 Cross-References....4615 Recommended Reading....4615 Visual Online Analytical Processing (OLAP)....4615 Synonyms....4615 Definition....4615 Historical Background....4616 Foundations....4618 Visual Query Specification....4619 Visualization Techniques....4620 Key Applications....4623 Future Directions....4623 Cross-References....4624 Recommended Reading....4624 Visual Perception....4625 Synonyms....4625 Definition....4625 Historical Background....4625 Foundations....4626 Key Applications....4628 Computer Graphics....4628 Artificial Intelligence....4628 Visual Interfaces....4628 Information Visualization....4628 Future Directions....4628 Experimental Results....4628 Data Sets....4629 URL to Code....4629 Cross-References....4629 Recommended Reading....4629 Visual Query Language....4629 Synonyms....4629 Definition....4629 Historical Background....4629 Foundations....4630 Key Applications....4633 Future Directions....4633 Temporal Databases....4633 Geographical Databases....4633 Web Visual Access....4634 Visually Querying Digital Libraries....4634 Experimental Results....4634 Cross-References....4635 Recommended Reading....4636 Visual Query Languages for Data Stream....4636 Synonyms....4636 Definition....4636 Historical Background....4637 Scientific Fundamentals....4637 Key Applications....4638 Future Directions....4639 Experimental Results....4639 Cross-References....4640 Recommended Reading....4640 Visual Representation....4640 Synonyms....4640 Definition....4640 Historical Background....4641 Foundations....4641 Data and Visual Models....4642 Visual Metaphors....4643 Datasets, Visualsets, and Visual Representation....4645 Key Applications....4645 Cross-References....4645 Recommended Reading....4645 Visualization for Information Retrieval....4646 Definition....4646 Historical Background....4646 Foundations....4647 Models for Multiple Reference Points....4647 Euclidean Space Characteristics Based Models....4648 Visualization of Hierarchy Structures....4649 Visualization of Internet Information....4649 Cross-References....4650 Recommended Reading....4650 Visualization Pipeline....4651 Synonyms....4651 Definition....4651 Key Points....4651 Cross-References....4652 Recommended Reading....4652 Visualizing Categorical Data....4652 Synonyms....4652 Definition....4652 Key Points....4653 Cross-References....4653 Recommended Reading....4653 Visualizing Clustering Results....4654 Synonyms....4654 Definition....4654 Historical Background....4654 Scientific Fundamentals....4657 Key Applications....4663 URL to Code....4663 Cross-References....4663 Recommended Reading....4663 Visualizing Hierarchical Data....4664 Synonyms....4664 Definition....4664 Historical Background....4665 Foundations....4665 Node-Edge Layouts....4665 Space-Filling Layouts....4667 Interactive Visualization of Hierarchical Data....4669 Key Applications....4670 Data Sets....4671 Cross-References....4671 Recommended Reading....4671 Visualizing Network Data....4671 Synonyms....4671 Definition....4671 Historical Background....4671 Foundations....4671 Node and Edge Representation....4672 Quality Criteria....4672 Layout Techniques....4673 Layouts for Networks with Data....4673 Interactive Augmentations....4674 Key Applications....4676 Future Directions....4676 Data Sets....4676 Cross-References....4677 Recommended Reading....4677 Visualizing Quantitative Data....4677 Synonyms....4677 Definition....4677 Key Points....4677 Cross-References....4678 Recommended Reading....4678 Volume....4678 Synonyms....4678 Definition....4678 Key Points....4678 Cross-References....4678 Voronoi Diagrams....4678 Synonyms....4678 Definition....4678 Key Points....4679 Cross-References....4680 Recommended Reading....4680 W....4681 W3C....4681 Synonyms....4681 Definition....4681 Key Points....4681 Cross-References....4681 Recommended Reading....4681 WAN Data Replication....4682 Synonyms....4682 Definition....4682 Historical Background....4682 Foundations....4683 Replica Placement....4683 Data Consistency....4684 Key Applications....4685 Cross-References....4686 Recommended Reading....4686 Wavelets on Streams....4686 Definition....4686 Historical Background....4687 Foundations ....4687 Key Applications....4692 Data Sets....4692 Future Directions....4692 Cross-References....4693 Recommended Reading....4693 Weak Consistency Models for Replicated Data....4693 Synonyms....4693 Definition....4693 Historical Background....4694 Foundations....4694 Key Applications....4697 Future Directions....4697 Cross-References....4697 Recommended Reading....4697 Weak Equivalence....4698 Synonyms....4698 Definition....4698 Key Points....4698 Cross-References....4698 Recommended Reading....4698 Web 2.0/3.0....4699 Definition....4699 Key Points....4699 Cross-References....4699 Web Advertising....4700 Synonyms....4700 Definition....4700 Historical Background....4700 Foundations....4700 Experimental Results....4702 Cross-References....4702 Recommended Reading....4702 Web Characteristics and Evolution....4703 Definition....4703 Historical Background....4703 Foundations....4704 Key Applications....4705 Data Sets....4705 Cross-References....4705 Recommended Reading....4705 Web Crawler Architecture....4706 Synonyms....4706 Definition....4706 Historical Background....4706 Foundations....4707 Key Applications....4708 Future Directions....4708 URL to Code....4709 Cross-References....4709 Recommended Reading....4709 Web Data Extraction System....4709 Synonyms....4709 Definition....4709 Historical Background....4710 Foundations....4710 Formal Foundations and Semantics of Data Extraction....4710 Methods of Wrapper Generation....4711 Architecture....4711 Commercial Wrapper Generation Systems....4713 Key Applications....4714 Future Directions....4714 Cross-References....4715 Recommended Reading....4715 Web ETL....4716 Synonyms....4716 Definitions....4716 Key Points....4716 Cross-References....4717 Recommended Reading....4717 Web Harvesting....4717 Synonyms....4717 Definition....4717 Key Points....4717 Cross-References....4718 Recommended Reading....4718 Web Information Extraction....4718 Synonyms....4718 Definition....4718 Historical Background....4719 Scientific Fundamentals....4719 Key Applications....4721 Future Directions....4722 Expressivity....4722 Extensibility....4723 Scalability....4724 Usability....4725 Cross-References....4726 Recommended Reading....4726 WEB Information Retrieval Models....4727 Synonyms....4727 Definition....4727 Historical Background....4728 Foundations....4728 Key Applications....4729 Future Directions....4730 Data Sets....4730 URL to Code....4731 Cross-References....4731 Recommended Reading....4731 Web Mashups....4732 Synonyms....4732 Definition....4732 Key Points....4732 Cross-References....4732 Web Page Quality Metrics....4732 Synonyms....4732 Definition....4732 Historical Background....4733 Foundations....4733 Key Applications....4734 Cross-References....4735 Recommended Reading....4735 Web Question Answering....4735 Synonyms....4735 Definition....4735 Historical Background....4736 Foundations....4736 Key Applications....4740 Data Sets....4740 Cross-References....4740 Recommended Reading....4740 Web Search Query Rewriting....4741 Synonyms....4741 Definition....4741 Historical Background....4741 Foundations....4742 Stemming....4742 Spelling Correction....4742 Query Expansion....4742 Query Substitution and Suggestion....4743 Query Word Deletion....4743 Key Applications....4743 Future Directions....4743 Cross-References....4743 Recommended Reading....4743 Web Search Relevance Feedback....4744 Definition....4744 Historical Background....4744 Foundations....4745 Key Applications....4747 Future Directions....4747 Experimental Results....4747 Data Sets....4748 URL to Code....4748 Cross-References....4748 Recommended Reading....4748 Web Search Relevance Ranking....4748 Synonyms....4748 Definition....4749 Historical Background....4749 Foundations....4749 Textual Relevance....4749 Hyperlink Relevance....4750 Exploiting User Behavior....4750 Performance....4751 Feature Combination....4751 Key Applications....4751 Future Directions....4751 Experimental Results....4752 Data Sets....4752 URL to Code....4752 Cross-References....4752 Recommended Reading....4752 Web Search Result Caching and Prefetching....4753 Synonyms....4753 Definition....4753 Historical Background....4754 Foundations....4754 Topical Locality of Reference....4754 Sequential Locality of Reference....4755 “Classic” Caching Schemes....4755 PDC – Probability Driven Cache....4756 SDC – Static Dynamic Cache....4756 AC....4756 Prefetching Policies....4756 Key Applications....4757 Future Directions....4757 Search Result Caching in Incremental Search Engines....4757 Caching in the Presence of Personalized Search Results....4757 Level of Details to Cache....4757 Holistic View....4757 Experimental Results....4757 Cross-References....4758 Recommended Reading....4758 Web Search Result De-duplication and Clustering....4759 Definition....4759 Historical Background....4759 Foundations....4760 Key Applications....4762 URL to Code....4763 Cross-References....4763 Recommended Reading....4763 Web Services....4764 Synonyms....4764 Definition....4764 Historical Background....4764 Foundations....4765 Key Applications....4766 Future Directions....4767 Cross-References....4767 Recommended Reading....4767 Web Services and the Semantic Web for Life Science Data....4767 Definitions....4767 Historical Background....4768 Foundations....4769 Web Services....4769 The Service Provider....4769 The Service Client....4770 The Service Registry....4770 The Semantic Web....4770 Ontologies....4770 Query Engines....4771 Inference Engines....4771 Semantic Web Services....4771 Semantic Web Services in the Life Sciences....4772 Key Applications....4773 Future Directions....4774 Cross-References....4774 Recommended Reading....4774 Web Spam Detection....4775 Synonyms....4775 Definition....4775 Historical Background....4775 Foundations....4776 Web Spam Detection as a Classification Problem....4776 Taxonomy of Web Spam Techniques....4776 Key Applications....4777 Future Directions....4778 Experimental Results....4778 Data Sets....4778 Cross-References....4778 Recommended Reading....4778 Web Transactions....4779 Synonyms....4779 Definition....4779 Key Points....4779 Cross-References....4779 Recommended Reading....4780 Web Views....4780 Synonyms....4780 Definition....4780 Key Points....4780 Cross-References....4781 Recommended Reading....4781 What-If Analysis....4781 Definition....4781 Historical Background....4781 Scientific Fundamentals....4782 Key Applications....4784 Future Directions....4784 Cross-References....4786 Recommended Reading....4786 WIMP Interfaces....4786 Definition....4786 Historical Background....4786 Foundations....4787 Windows....4787 Icons....4787 Pointers....4789 Menus....4789 Additional Interaction Elements....4790 Key Applications....4790 Cross-References....4790 Recommended Reading....4790 Window Operator in RDBMS....4791 Synonyms....4791 Definition....4791 Historical Background....4792 Evaluation Techniques....4792 Key Applications....4792 Cross-References....4792 Recommended Reading....4792 Window-Based Query Processing....4793 Synonyms....4793 Definition....4793 Historical Background....4793 Foundations....4793 Query Processing Techniques: Incremental Evaluation Versus Reevaluation....4794 Query Reevaluation....4794 Query Processing Using Revision Tuples....4794 Query Processing Using Punctuations....4794 Query Processing Using Heartbeats....4794 Incremental Query Evaluation....4795 Incremental Query Processing Using Negative Tuples....4795 Query Processing for Predicate Windows....4796 Shared Execution of Multiple Window-Based Queries....4796 Out-of-Order Tuple Processing....4797 Key Applications....4797 Cross-References....4798 Recommended Reading....4798 Windows....4798 Synonyms....4798 Definition....4799 Key Points....4799 Cross-References....4799 Recommended Reading....4800 Workflow Constructs....4800 Synonyms....4800 Definition....4800 Key Points....4800 Cross-References....4800 Workflow Evolution....4800 Synonyms....4800 Definition....4800 Historical Background....4801 Foundations....4802 Key Applications....4804 Future Directions....4805 Cross-References....4805 Recommended Reading....4805 Workflow Join....4806 Synonyms....4806 Definition....4806 Key Points....4806 Cross-References....4806 Workflow Management....4806 Synonyms....4806 Definition....4806 Key Points....4807 Cross-References....4807 Workflow Management and Workflow Management System....4807 Synonyms....4807 Definition....4807 Historical Background....4807 Scientific Fundamentals....4808 Key Applications....4810 Future Directions....4812 Cross-References....4812 Recommended Reading....4812 Workflow Management Coalition....4812 Synonyms....4812 Definition....4812 Key Points....4813 Cross-References....4813 Workflow Management Systems....4813 Synonyms....4813 Definition....4813 Workflow Model....4813 Cross-References....4813 Recommended Reading....4814 Workflow Model....4814 Synonyms....4814 Definition....4814 Key Points....4814 Cross-References....4814 Workflow Model Analysis....4814 Definition....4814 Key Points....4814 Cross-References....4815 Recommended Reading....4815 Workflow Patterns....4815 Definition....4815 Historical background....4816 Cross-References....4816 Recommended Reading....4816 Workflow Schema....4817 Synonyms....4817 Definition....4817 Key Points....4817 Cross-References....4817 Workflow Transactions....4817 Synonyms....4817 Definition....4817 Key Points....4817 Cross-References....4818 Recommended Reading....4818 Wrapper Induction....4818 Synonyms....4818 Definition....4818 Historical Background....4818 Foundations....4819 From Free Text to Web Documents....4819 Wrapper Induction....4820 Patterns and Output Structure....4820 Kushmerick's Wrapper Classes....4821 Other Wrapper Classes....4821 Active Learning....4822 Key Applications....4822 Wrapper Induction Algorithms....4822 Future Directions....4823 Data Sets....4824 Cross-References....4824 Recommended Reading....4824 Wrapper Maintenance....4824 Synonyms....4824 Definition....4824 Historical Background....4825 Foundations....4825 Wrapper Verification....4826 Wrapper Reinduction....4827 Key Applications....4827 Experimental Results....4827 Data Sets....4828 Cross-References....4828 Recommended Reading....4828 Wrapper Stability....4829 Synonyms....4829 Definition....4829 Key Points....4829 Cross-References....4829 Recommended Reading....4829 Write Once Read Many....4830 Synonyms....4830 Definition....4830 Key Points....4830 Cross-References....4830 X....4831 XML....4831 Synonyms....4831 Definition....4831 Historical Background....4831 Foundations....4831 Key Applications....4832 Cross-References....4833 Recommended Reading....4833 XML Access Control....4833 Definition....4833 Historical Background....4833 Foundations....4834 Key Applications....4836 Recommended Reading....4836 XML Attribute....4836 Synonyms....4836 Definition....4837 Key Points....4837 Cross-References....4837 Recommended Reading....4837 XML Benchmarks....4837 Definition....4837 Historical Background....4837 Foundations....4838 XML Microbenchmarks....4838 The Michigan Benchmark....4838 XML Application Benchmarks....4838 XMach-1....4838 XMark....4839 XBench....4839 TPoX....4839 Synthetic Data Generators....4839 Key Applications....4840 Recommended Reading....4840 XML Compression....4840 Definition....4840 Historical Background....4841 Foundations....4841 Compression-Oriented XML Compressors....4842 Query-Oriented XML Compressors....4843 Key Applications....4845 Cross-References....4845 Recommended Reading....4845 XML Document....4846 Synonyms....4846 Definition....4846 Key Points....4846 Cross-References....4846 Recommended Reading....4846 XML Element....4846 Synonyms....4846 Definition....4846 Key Points....4847 Cross-References....4847 Recommended Reading....4847 XML Indexing....4847 Definition....4847 Historical Background....4847 Foundations....4847 Notation....4847 Node Indexes....4849 Positional Numberings, Edge Indexes....4849 Using Node Ids....4849 Using Dewey Numbering....4849 Using Interval Numbering....4850 Path Indexes....4850 Twig Indexes....4851 Key Applications....4851 Future Directions....4852 Data Sets....4852 Cross-References....4852 Recommended Reading....4852 XML Information Integration....4853 Synonyms....4853 Definition....4853 Key Points....4853 Key Applications....4853 Cross-References....4853 Recommended Reading....4853 XML Integrity Constraints....4854 Synonyms....4854 Definition....4854 Historical Background....4854 Foundations....4855 Keys and Functional Dependencies for XML....4856 Inclusion Dependencies and Foreign Keys for XML....4858 Key Applications....4859 Cross-References....4859 Recommended Reading....4859 XML Metadata Interchange....4860 Synonyms....4860 Definition....4860 Key Points....4860 Cross-References....4860 Recommended Reading....4860 XML Parsing, SAX/DOM....4860 Definition....4860 Historical Background....4861 Foundations....4861 XML Programming Interfaces....4861 Validating Parsers....4862 XML Parsing Performance....4863 Key Applications....4863 URL to Code....4864 List of XML Parsing Interfaces....4864 List of XML Parsers....4864 Cross-References....4864 Recommended Reading....4864 XML Process Definition Language....4864 Synonyms....4864 Definition....4864 Key Points....4865 Cross-References....4865 XML Programming....4865 Synonyms....4865 Definition....4865 Historical Background....4865 Foundations....4866 Specific Requirements of XML Programming....4866 Conceptual Aspects of XML....4866 Differences in XML Usage....4867 Additional Classification Criteria....4868 Approaches to XML Programming....4869 Key Applications....4871 Future Directions....4872 Cross-References....4872 Recommended Reading....4872 XML Publish/Subscribe....4872 Synonyms....4872 Definition....4873 Historical Background....4873 Foundations....4873 Foundation of XML Stream Processing for Publish/Subscribe....4873 XML Filtering....4874 XML Filtering and Transformation....4876 Stateful XML Publish/Subscribe....4876 XML Routing....4876 Key Applications....4877 Data Sets....4877 URL to Code....4878 Cross-References....4878 Recommended Reading....4878 XML Publishing....4878 Synonyms....4878 Definition....4878 Historical Background....4879 Foundations....4879 Converting Queries....4879 Composition and Optimization....4880 Adding Tags....4880 In-Engine Tagging....4881 Tagging Middleware....4881 Key Applications....4881 Cross-References....4882 Recommended Reading....4882 XML Retrieval....4882 Synonyms....4882 Definition....4882 Historical Background....4883 Foundations....4883 Query Languages....4883 Indexing Strategies....4884 Ranking Strategies....4885 Key Applications....4886 Experimental Results....4886 Data Sets....4887 Cross-References....4887 Recommended Reading....4887 XML Schema....4887 Synonyms....4887 Definition....4887 Key Points....4889 Cross-References....4889 Recommended Reading....4889 XML Selectivity Estimation....4889 Synonyms....4889 Definition....4890 Historical Background....4890 Foundations....4890 Path Enumeration....4891 Graph-Synopsis-Based Techniques....4892 Updatable Synopses....4893 Key Applications....4893 Cross-References....4893 Recommended Reading....4893 XML Storage....4894 Synonyms....4894 Definition....4894 Historical Background....4894 Foundations....4895 Instance-Driven Storage....4896 Tabular Storage of Trees....4896 Native XML Storage....4897 Schema-Driven Storage....4897 Relational Storage for XML Documents....4898 Cost-Based Approaches....4898 Correctness and Losslessness....4899 Order Encoding Schemes....4899 Hybrid XML Storage....4900 Key Applications....4900 Cross-References....4900 Recommended Reading....4901 XML Stream Processing....4901 Definition....4901 Historical Background....4901 Foundations....4902 Key Applications....4904 Cross-References....4904 Recommended Reading....4904 XML Tree Pattern, XML Twig Query....4905 Synonyms....4905 Definition....4905 Historical Background....4905 Foundations....4906 Key Applications....4906 Cross-References....4907 Recommended Reading....4907 XML Tuple Algebra....4908 Synonyms....4908 Definition....4908 Historical Background....4909 Foundations....4909 Unified Data Model....4909 Unified Algebra....4910 Selection....4910 Projection....4910 Navigation....4911 Construction....4912 Nested Plans....4912 Apply....4912 Group-by....4912 Apply-on-Set....4913 Key Applications....4914 Cross-References....4914 Recommended Reading....4914 XML Typechecking....4915 Definition....4915 Historical Background....4915 Foundations....4916 Exact Typechecking....4916 XML-to-XML Transformations....4916 XML Publishing....4916 Approximate Typechecking....4917 Type Systems....4917 Flow-Analysis....4918 Key Applications....4918 URL to Code....4918 Cross-References....4919 Recommended Reading....4919 XML Types....4920 Synonyms....4920 Definition....4920 Historical Background....4920 Foundations....4920 Intuition....4920 A Formalization of Relax NG....4922 Relationship with Tree and Hedge Automata....4922 Deterministic Regular Expressions....4923 A Formalization of DTDs and XSDs....4923 Expressiveness and Complexity....4923 Cross-References....4924 Recommended Reading....4924 XML Updates....4924 Synonyms....4924 Definition....4924 Historical Background....4924 Scientific Fundamentals....4925 Key Applications....4926 Future Directions....4926 Experimental Results....4926 Cross-References....4926 Recommended Reading....4926 XML Views....4927 Synonyms....4927 Definition....4927 Historical Background....4927 Foundations....4927 Mapping Between the XML View and the Underlying Data....4928 User Queries Over XML Views....4928 User Updates Over XML Views....4929 Maintenance of Materialized XML Views....4929 Key Applications....4930 Future Directions....4930 Cross-References....4931 Recommended Reading....4931 XPath/XQuery....4931 Synonyms....4931 Definition....4931 Historical Background....4932 XPath 1.0....4932 XQuery 1.0 and XPath 2.0....4932 Historical Roots of XQuery 1.0....4932 Foundations....4932 The XPath 1.0 Data Model....4932 The XPath 1.0 Language....4933 XQuery 1.0....4935 XPath 2.0....4937 Key Applications....4937 Future Directions....4937 The XQuery Update Facility....4937 XQuery 1.1 and XPath 2.1....4937 XQuery 1.0 and XPath 2.0 Full-Text....4938 XQuery Scripting Extensions....4938 Cross-References....4938 Recommended Reading....4938 XQuery Full-Text....4938 Synonyms....4938 Definition....4938 Historical Background....4939 Foundations....4939 XQuery Full-Text Integration....4939 XQuery Full-Text Query Primitives....4940 XQuery Full-Text Formal Model....4942 Relevance Scoring in XQuery Full-Text....4943 Key Applications....4943 Cross-References....4944 Recommended Reading....4944 XQuery Processors....4944 Synonyms....4944 Definition....4944 Historical Background....4944 Foundations....4945 Pathfinder: Purely Relational XQuery....4945 Timber: A Native XML Database System....4946 DB2 XML: A Hybrid Relational and XML DBMS....4948 Key Applications....4949 URL to Code....4949 Pathfinder....4949 Timber....4949 Cross-References....4949 Recommended Reading....4949 XSL/XSLT....4950 Synonyms....4950 Definition....4950 Historical Background....4950 Foundations....4951 XSLT Programming....4951 XSL-FO Document Typesetting....4953 Theoretical Foundations of XSLT....4953 XSLT and XQuery....4954 XSLT Data Processing....4954 Key Applications....4955 Information Publishing....4955 Data Exchange and Service Integration....4955 Model Exchange and Transformation....4955 Url to Code....4955 Cross-References....4956 Recommended Reading....4956 Z....4957 Zero-One Laws....4957 Definition....4957 Key Points....4957 Cross-References....4958 Recommended Reading....4958 Zooming Techniques....4958 Synonyms....4958 Definition....4958 Historical Background....4958 Foundations....4960 Navigation in Information Spaces....4960 Interaction Techniques....4961 Zoom Granularity and Manipulation....4961 Transition Between Zooming....4963 Key Applications....4963 Future Directions....4963 Experimental Results....4963 Cross-References....4963 Recommended Reading....4964