Search

Learned indexes have attracted significant research interest due to their ability to offer better space-time trade-offs compared to traditional B+-tree variants. Among various learned indexes, the PGM-Index based on error-bounded piecewise linear approximation is an elegant data structure that has demonstrated \emph{provably} superior performance over conventional B+-tree indexes. In this paper, we explore two interesting research questions regarding the PGM-Index: (a) \emph{Why are PGM-Indexes theoretically effective?} and (b) \emph{Why do PGM-Indexes underperform in practice?} For question~(a), we first prove that, for a set of $N$ sorted keys, the PGM-Index can, with high probability, achieve a lookup time of $O(\log\log N)$ while using $O(N)$ space. To the best of our knowledge, this is the \textbf{tightest bound} for learned indexes to date. For question~(b), we identify that querying PGM-Indexes is highly memory-bound, where the internal error-bounded search operations often become the bottleneck. To fill the performance gap, we propose PGM++, a \emph{simple yet effective} extension to the original PGM-Index that employs a mixture of different search strategies, with hyper-parameters automatically tuned through a calibrated cost model. Extensive experiments on real workloads demonstrate that PGM++ establishes a new Pareto frontier. At comparable space costs, PGM++ speeds up index lookup queries by up to $\mathbf{2.31\times}$ and $\mathbf{1.56\times}$ when compared to the original PGM-Index and state-of-the-art learned indexes.

Efficient indexing is fundamental for multi-dimensional data management and analytics. An emerging tendency is to directly learn the storage layout of multi-dimensional data by simple machine learning models, yielding the concept of Learned Index. Compared with the conventional indices used for decades (e.g., kd-tree and R-tree variants), learned indices are empirically shown to be both space- and time-efficient on modern architectures. However, there lacks a comprehensive evaluation of existing multi-dimensional learned indices under a unified benchmark, which makes it difficult to decide the suitable index for specific data and queries and further prevents the deployment of learned indices in real application scenarios. In this paper, we present the first in-depth empirical study to answer the question of how good multi-dimensional learned indices are. Six recently published indices are evaluated under a unified experimental configuration including index implementation, datasets, query workloads, and evaluation metrics. We thoroughly investigate the evaluation results and discuss the findings that may provide insights for future learned index design.

We report direct visualization of gigahertz-frequency Lamb waves propagation in aluminum nitride phononic circuits by transmission-mode microwave impedance microscopy (TMIM). Consistent with the finite-element modeling, the acoustic eigenmodes in both a horn-shaped coupler and a sub-wavelength waveguide are revealed in the TMIM images. Using fast Fourier transform filtering, we quantitatively analyze the acoustic loss of individual Lamb modes along the waveguide and the power coupling coefficient between the waveguide and the parabolic couplers. Our work provides insightful information on the propagation, mode conversion, and attenuation of acoustic waves in piezoelectric nanostructures, which is highly desirable for designing and optimizing phononic devices for microwave signal processing and quantum information transduction., Comment: 14 pages, 7 figures

We consider a community finding problem called Co-located Community Detection (CCD) over geo-social networks, which retrieves communities that satisfy both high structural tightness and spatial closeness constraints. To provide a solution that benefits from existing studies on community detection, we decouple the spatial constraint from graph structural constraint and propose a uniform CCD framework which gives users the freedom to choose customized measurements for social cohesiveness (e.g., $k$-core or $k$-truss). For the spatial closeness constraint, we apply the bounded radius spatial constraint and develop an exact algorithm together with effective pruning rules. To further improve the efficiency and make our framework scale to a very large scale of data, we propose a near-linear time approximation algorithm with a constant approximation ratio ($\sqrt{2}$). We conduct extensive experiments on both synthetic and real-world datasets to demonstrate the efficiency and effectiveness of our algorithms.

In the well-known stimulated Brillouin scattering (SBS) process, spontaneous acoustic phonons in materials are stimulated by laser light and scatter the latter into a Stokes sideband. SBS becomes more pronounced in optical fibers and has been harnessed to amplify optical signals and even achieve lasing. Exploitation of SBS has recently surged on integrated photonics platforms as simultaneous confinement of photons and phonons in waveguides leads to drastically enhanced interaction. Instead of being optically stimulated, coherent phonons can also be electromechanically excited with very high efficiency as has been exploited in radiofrequency acoustic filters. Here, we demonstrate electromechanically excited Brillouin scattering in integrated optomechanical waveguides made of piezoelectric material aluminum nitride (AlN). Acoustic phonons of 16 GHz in frequency are excited with nanofabricated electromechanical transducers to scatter counter-propagating photons in the waveguide into a single anti-Stokes sideband. We show that phase-matching conditions of Brillouin scattering can be tuned by varying both the optical wavelength and the acoustic frequency to realize tunable single-sideband modulation. Combining Brillouin scattering photonics with nanoelectromechanical systems, our approach provides an efficient interface between microwave and optical photons that will be important for microwave photonics and potentially quantum transduction., Comment: 13 pages, 4 figures

Integrating nanoscale electromechanical transducers and nanophotonic devices potentially can enable new acousto-optic devices to reach unprecedented high frequencies and modulation efficiency. Here, we demonstrate acousto-optic modulation of a photonic crystal nanocavity using Lamb waves with frequency up to 19 GHz, reaching the microwave K band. The devices are fabricated in suspended aluminum nitride membrane. Excitation of acoustic waves is achieved with interdigital transducers with periods as small as 300 nm. Confining both acoustic wave and optical wave within the thickness of the membrane leads to improved acousto-optic modulation efficiency in the new devices than that obtained in previous surface acoustic wave devices. Our system demonstrates a novel scalable optomechanical platform where strong acousto-optic coupling between cavity-confined photons and high frequency traveling phonons can be explored.

Sideband-resolved coupling between multiple photonic nanocavities and propagating mechanical waves in microwave Ku-band is demonstrated. Coherent and strong photon-phonon interaction is manifested with optomechanically induced transparency and absorption, and phase-coherent interaction in multiple cavities. Inside an echo chamber it is shown that a phonon pulse can interact with an embedded nanocavity for multiple times. Our device provides a scalable platform to optomechanically couple phonons and photons for microwave photonics and quantum photonics., Comment: 16 pages, 5 figures