Buffering Accesses to Memory-Resident Index Structures
Recent studies have shown that cache-conscious indexes outperform conventional main memory indexes. Cache-conscious indexes focus on better utilization of each cache line for improving search performance of a single lookup. None has exploited cache spatial and temporal locality between consecutive lookups. We show that conventional indexes, even "cache-conscious" ones, suffer from significant cache thrashing between accesses. Such thrashing can impact the performance of applications such as stream processing and query operations such as index-nested-loops join. 
 
We propose techniques to buffer accesses to memory-resident tree-structured indexes to avoid cache thrashing. We study several alternative designs of the buffering technique, including whether to use fixed-size or variable-sized buffers, whether to buffer at each tree level or only at some of the levels, how to support bulk access while there are concurrent updates happening to the index, and how to preserve the order of the incoming lookups in the output results. Our methods improve cache performance for both cache-conscious and conventional index structures. Our experiments show that buffering techniques enable a probe throughput that is two to three times higher than traditional methods.

title: Implementing database operations using SIMD instructions
abstract: Modern CPUs have instructions that allow basic operations to be performed on several data elements in parallel. These instructions are called SIMD instructions, since they apply a single instruction to multiple data elements. SIMD technology was initially built into commodity processors in order to accelerate the performance of multimedia applications. SIMD instructions provide new opportunities for database engine design and implementation. We study various kinds of operations in a database context, and show how the inner loop of the operations can be accelerated using SIMD instructions. The use of SIMD instructions has two immediate performance benefits: It allows a degree of parallelism, so that many operands can be processed at once. It also often leads to the elimination of conditional branch instructions, reducing branch mispredictions.We consider the most important database operations, including sequential scans, aggregation, index operations, and joins. We present techniques for implementing these using SIMD instructions. We show that there are significant benefits in redesigning traditional query processing algorithms so that they can make better use of SIMD technology. Our study shows that using a SIMD parallelism of four, the CPU time for the new algorithms is from 10% to more than four times less than for the traditional algorithms. Superlinear speedups are obtained as a result of the elimination of branch misprediction effects.

title: Buffering databse operations for enhanced instruction cache performance
abstract: As more and more query processing work can be done in main memory access is becoming a significant cost component of database operations. Recent database research has shown that most of the memory stalls are due to second-level cache data misses and first-level instruction cache misses. While a lot of research has focused on reducing the data cache misses, relatively little research has been done on improving the instruction cache performance of database systems.We first answer the question "Why does a database system incur so many instruction cache misses?" We demonstrate that current demand-pull pipelined query execution engines suffer from significant instruction cache thrashing between different operators. We propose techniques to buffer database operations during query execution to avoid instruction cache thrashing. We implement a new light-weight "buffer" operator and study various factors which may affect the cache performance. We also introduce a plan refinement algorithm that considers the query plan and decides whether it is beneficial to add additional "buffer" operators and where to put them. The benefit is mainly from better instruction locality and better hardware branch prediction. Our techniques can be easily integrated into current database systems without significant changes. Our experiments in a memory-resident PostgreSQL database system show that buffering techniques can reduce the number of instruction cache misses by up to 80% and improve query performance by up to 15%.

title: Architecture Sensitive Database Design: Examples from the Columbia Group
abstract: In this article, we discuss how different aspects of modern CPU architecture can be effectively used by database systems. While we shall try to cover most important aspects of modern architectures, we shall not aim to provide an exhaustive survey of the literature. Rather, we will use examples from our own recent work to illustrate the principles involved. While there is related work on using other components of modern machines such as graphics cards and intelligent disk controllers for database work, we limit our discussion here to just a single CPU and the memory hierarchy (excluding disks). In recent years the primary focus of database performance research has fundamentally shifted from disks to main memory. Systems with a very large main memory allow a database’s working set to fit in RAM. At the same time processors have continued to double in performance roughly every eighteen months in line with “Moore’s Law,” while memory speed improvements have been marginal. The CPU now spends many hundreds of cycles waiting for data to arrive from main memory, and database workloads are often memory-bound. Because of this bottleneck, database research at Columbia and elsewhere has focused on effectively using the cache hierarchy to improve database performance. Changes in processor technology have also influenced database research. Modern processors feature a very long pipeline, which helps to provide better performance. It also results in a higher branch misprediction penalty, because the pipeline must be flushed and restarted when a branch is mispredicted. Modern CPUs provide the database programmer with a rich instruction set. Using specialized instructions, such as SIMD instructions, database performance can be improved by allowing a degree of parallelism and eliminating some conditional branch instructions, thus reducing the impact of branch mispredictions.

title: Transparent mid-tier database caching in SQL server
abstract: Many applications today run in a multi-tier environment with browser-based clients, mid-tier (application) servers and a backend database server. Mid-tier database caching attempts to improve system throughput and scalability by offloading part of the database workload to intermediate database servers that partially replicate data from the backend server. The fact that some queries are offloaded to an intermediate server should be completely transparent to applications one of the key distinctions between caching and replication. MTCache is a prototype mid-tier database caching solution for SQL Server that achieves this transparency. It builds on SQL Server's support for materialized views, distributed queries and replication. This paper describes MTCache and reports experimental results on the TPC-W benchmark. The experiments show that a significant part of the query workload can be offloaded to cache servers, resulting in greatly improved scale-out on the read-dominated workloads of the benchmark. Replication overhead was small with an average replication delay of less than two seconds.

title: Data driven approach to designing minimum hamming distance polychotomizer
abstract: A polychotomous classifier assigns an observation to one of the K categories with K > = 3. Multiple binary classifiers (K = 2) such as the popular Support Vector Machines can be combined to achieve multi-class classification. Commonly used approaches include the one-vs-others scheme and the one-vs-one (pairwise coupling) scheme. While literature reported better performance from pairwise coupling than one-vs-others, the number of base learners required by pairwise coupling is quadratic in K. Alternatively, error correcting output codes (ECOC) provides a more general framework for designing polychotomizers. It associates each class with a codeword, which provides the capability to unify the traditional schemes. However, the design of an effective "coding matrix" remains an open problem. We study one kind of ECOC polychotomizer that decodes using minimum hamming distance. We propose a novel data-driven way to design the codewords based on inter-cluster distance. It provides a systematic way to extend the traditional schemes and construct effective polychotomizers. Experiments are conducted on synthetic data and real world applications including UCI repository problems and CENPARMI handwritten numerals. Experiments show that the proposed scheme can achieve competitive accuracy compared with both traditional schemes, and the number of base learners is typically much less than the requirement of the pairwise scheme.

title: Defending against redirect attacks in mobile IP
abstract: The route optimization operation in Mobile IP Version 6 (MIPv6) allows direct routing from any correspondent node to any mobile node and thus eliminates the problem of "triangle routing" present in the base Mobile IP Version 4 (MIPv4) protocol. Route optimization, however, requires that a mobile node constantly inform its correspondent nodes about its new care-of addresses by sending them binding update messages. Unauthenticated or malicious binding updates open the door for intruders to perform redirect attacks, i.e., malicious acts which redirect traffic from correspondent nodes to locations chosen by intruders. How to protect binding update messages to defend against redirect attacks is a challenging problem given the open environment in which MIPv6 operates. In this paper, we first look at two solutions proposed by the IETF Mobile IP Working Group and point out their weaknesses. We then present a new protocol for securing binding update messages. We also show that our protocol achieves strong security and at the same time is highly scalable to wide spread deployment.

title: Recognition of handwritten numerals by Quantum Neural Network with fuzzy features
abstract: This paper describes a new kind of neural network – Quantum Neural Network (QNN) – and its application to the recognition of handwritten numerals. QNN combines the advantages of neural modelling and fuzzy theoretic principles. Novel experiments have been designed for in-depth studies of applying the QNN to both real data and confusing images synthesized by morphing. Tests on synthesized data examine QNN's fuzzy decision boundary with the intention to illustrate its mechanism and characteristics, while studies on real data prove its great potential as a handwritten numeral classifier and the special role it plays in multi-expert systems. An effective decision-fusion system is proposed and a high reliability of 99.10% has been achieved.

title: TWINE: A Hybrid Emulation Testbed for Wireless Networks and Applications
abstract: In this paper, we present TWINE, a high fidelity, efficient emulation framework that combines the accuracy and realism of emulated and physical networks and the scalability and repeatability of simulation in an integrated testbed, for evaluation of real protocols and applications. Our measurements show that the TWINE emulation kernel has a memory footprint of less than 100KB, and occupies no more than 3.5% CPU cycles. Thanks to such small overhead and the accurate modelling of physical layer events(at microseconds level), application throughput measured in TWINE is within 5% of the measured throughput from an equivalent physical wireless LAN. A single commodity PC in TWINE can emulate at least four wireless hosts or simulate sixty nodes in real time at microseconds granularity. This paper also illustrates TWINE’s novel capabilities via two case studies: a protocol to maintain fairness in mesh networks and an adaptive streaming media application operating in heterogeneous wireless networks. The results from the case studies clearly show the benefit of the TWINE evaluation methodology, by identifying a mismatch between the performance of the protocol or application based on actual user experience versus its performance as measured using traditional network performance metrics such as application throughput.

title: Analysis of a free roaming agent result-truncation defense scheme
abstract: Mobile agents play an important role in electronic commerce. Security in free-roaming agents is especially hard to achieve when the mobile code is executed in hosts that may behave maliciously. Some schemes have been proposed to protect agent data (or computation results). However, a known vulnerability of these techniques is the truncation attack where two visited hosts (or one revisited host) can collude to discard the partial results collected between their respective visits. Cheng and Wei proposed a scheme in IC1CS'O2 to defense against the truncation of computation results of free-roaming agents (Cheng and Wei, 2002). Cheng-Wei scheme is effective against such an attack in most cases. However, we demonstrate that it still suffers from the truncation attack when a special loop is established on the path of a free-roaming agent. We further propose two amendments to Cheng-Wei scheme to avoid such an attack.