More Like this

1. Skip-Sliding Window Codes

   https://doi.org/10.1109/TCOMM.2021.3058965  

   Wu, Ting-Yi; Tandon, Anshoo; Varshney, Lav R.; Motani, Mehul (May 2021, IEEE Transactions on Communications)

   null (Ed.)
2. Write-Optimized Skip Lists

   https://doi.org/10.1145/3034786.3056117  

   Bender, Michael; Farach-Colton, Martin; Johnson, Rob; Mauras, Simon; Mayer, Tyler; Phillips, Cynthia; Xu, Helen (January 2017, PODS '17 Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems)

   The skip list is an elegant dictionary data structure that is com- monly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(logN) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p. A seemingly natural way to generalize the skip list to external memory with block size B is to “promote” with probability 1/B, rather than 1/2. However, there are practical and theoretical obsta- cles to getting the skip list to retain its efficient performance, space bounds, and high-probability guarantees. We give an external-memory skip list that achieves write- optimized bounds. That is, for 0 < ε < 1, range queries take O(logBε N + K/B) I/Os w.h.p. and insertions and deletions take O((logBε N)/B1−ε) amortized I/Os w.h.p. Our write-optimized skip list inherits the virtue of simplicity from RAM skip lists. Moreover, it matches or beats the asymptotic bounds of prior write-optimized data structures such as Bε trees or LSM trees. These data structures are deployed in high-performance databases and file systems. 

   more » « less
3. Skip-sampling: subsampling in the frequency domain

   McElroy, T; Politis, D (September 2024, Biometrika)
4. SkipGNN: predicting molecular interactions with skip-graph networks

   https://doi.org/10.1038/s41598-020-77766-9  

   Huang, Kexin; Xiao, Cao; Glass, Lucas M.; Zitnik, Marinka; Sun, Jimeng (December 2020, Scientific Reports)

   null (Ed.)

   Abstract Molecular interaction networks are powerful resources for molecular discovery. They are increasingly used with machine learning methods to predict biologically meaningful interactions. While deep learning on graphs has dramatically advanced the prediction prowess, current graph neural network (GNN) methods are mainly optimized for prediction on the basis of direct similarity between interacting nodes. In biological networks, however, similarity between nodes that do not directly interact has proved incredibly useful in the last decade across a variety of interaction networks. Here, we present SkipGNN, a graph neural network approach for the prediction of molecular interactions. SkipGNN predicts molecular interactions by not only aggregating information from direct interactions but also from second-order interactions, which we call skip similarity. In contrast to existing GNNs, SkipGNN receives neural messages from two-hop neighbors as well as immediate neighbors in the interaction network and non-linearly transforms the messages to obtain useful information for prediction. To inject skip similarity into a GNN, we construct a modified version of the original network, called the skip graph. We then develop an iterative fusion scheme that optimizes a GNN using both the skip graph and the original graph. Experiments on four interaction networks, including drug–drug, drug–target, protein–protein, and gene–disease interactions, show that SkipGNN achieves superior and robust performance. Furthermore, we show that unlike popular GNNs, SkipGNN learns biologically meaningful embeddings and performs especially well on noisy, incomplete interaction networks. 

   more » « less
5. NUMASK: High Performance Scalable Skip List for NUMA

   Henry Daly, Ahmed Hassan (May 2019, 32nd International Symposium on Distributed Computing)