Skip to content

Latest commit

 

History

History
193 lines (168 loc) · 19.3 KB

Algorithms.md

File metadata and controls

193 lines (168 loc) · 19.3 KB
Raw

ALGORITHMS and Data Structures : Data Mining, Clustering, ...

ALGORITHMS

Association Rule

  • ARules.jl :: Julia package for Association Rule Learning algorithms.

Checksum

  • CRC.jl :: This is a Julia module for calculating Cyclic Redundancy Checksums (CRCs).
  • CRC32.jl :: 32-bit cyclic redundancy check (CRC-32) checksum implementation.

Collaborative Filtering

  • RecSys.jl :: An implementation of the algorithm from Yunhong Zhou, Dennis Wilkinson, Robert Schreiber and Rong Pan. Large-Scale Parallel Collaborative Filtering for the Netflix Prize. Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management. Shanghai, China pp. 337-348, 2008.

Scheduling Algorithm

  • HClust.jl :: Hierarchical Clustering for Julia, similar to R's hclust().

Quantum

  • AdiaRoll.jl :: An Adiabatic Computation Simulator for quantum computation.
  • Hadamard.jl :: Fast multidimensional Walsh-Hadamard transforms.

Pattern Matching

  • AhoCorasick.jl :: Julia implementation of the Aho-Corasick algorithm for fast string searching.
  • association_rules_jl :: This package implements algorithms for association rule mining and sequential pattern mining, viz., the Apriori algorithm (Agrawal & Srikant, 1994) and the SPADE algorithm (Zaki, 2001). The former is used for association rule mining (e.g., "market basket" analysis), and the latter is used for identifying sequential patterns when the data possess a temporal ordering.
  • bfs.jl :: Breadth First Search implementation in Julia.
  • BlossomV.jl :: An interface for the Blossom V perfect matching algorithm.
  • dfs.jl :: Depth First Search.
  • ExpressionMatch.jl :: A small library designed to help macro writers deconstruct Julia expressions in a more declarative way without having to know in great detail how syntax is represented internally.
  • JellyFish.jl :: Port of the jellyfish string comparison library.
  • Loess.jl :: is a loess implementation based on the fast kd-tree based approximation algorithm, a space-partitioning data structure for organizing points in a k-dimensional space.
  • Match.jl :: Advanced Pattern Matching for Julia.
  • NearestNeighbors.jl :: Data structures for nearest neighbor search.
  • ReverseRegexes.jl :: Adds functionality to reverse-search strings with regexes

Sorting

Time

  • LabelPropagation.jl :: A fast, nearly linear time algorithm for detecting communtiy structure in networks.
RESOURCES

COMPUTATIONAL PROBLEMS

NP-complete

SAT

  • dReal.jl :: Nonlinear SMT solving using dReal.
  • PicoSAT.jl :: Provides Julia bindings to the popular SAT solver picosat by Armin Biere. It is based off the Python pycosat and Go pigosat bindings written by Ilan Schnell and Willam Schwartz.
  • Z3.jl :: This is a Julia interface to Z3 - a high performance theorem prover developed at Microsoft Research. Z3 can solve satisfiability modulo theory (SMT) problems.

DATA STRUCTURES

Array-Matrix

  • ArrayIteration.jl :: Testing new ideas for array iteration.
  • ArrayViews.jl :: A Julia package to explore a new system of array views.
  • ArrayViewsAPL.jl :: Generic array-view type with APL indexing semantics.
  • AxisArrays.jl :: Performant arrays where each dimension can have a named axis with values.
  • BandedMatrices.jl :: A Julia package for representing banded matrices.
  • CatIndices.jl :: Julia package for indices-aware array concatenation and growth.
  • CategoricalArrays.jl :: Arrays for working with categorical data (both nominal and ordinal) in Julia.
  • ChunkedArrays.jl :: A package for increasing the performance of arrays generated.
  • EndpointRanges.jl :: Julia package for doing arithmetic on endpoints in array indexing.
  • FArrayMod.jl :: provides the ability to use arbitrary starting indices for arrays in Julia programming language.
  • FlexibleArrays.jl :: Multi-dimensional arrays with arbitrary upper and lower bounds that can be fixed or flexible. Source Code.
  • FreqTables.jl :: Frequency tables in Julia.
  • HMat.jl :: Hierarchical Matrix.
  • ImmutableArrays.jl :: Statically-sized immutable vectors and matrices.
  • IndexedArrays.jl :: A data structure that acts like a Vector of unique elements allowing a quick lookup of the index of any vector element in the array.
  • IndexedTables.jl :: N-dimensional sparse array structure in julia.
  • IndirectArrays.jl :: Julia implementation of indexed or "lookup" arrays.
  • JuliaDB.jl :: A package based on Dagger and IndexedTables, provides a distributed-array-like data model for working with large persistent data sets. Given a set of CSV files, it builds and saves an index that allows the data to be accessed efficiently in the future. It also supports an "ingest" mode that converts data to a more efficient binary format.
  • JudyDicts.jl :: Judy Array for Julia.
  • julia-delayed-matrix :: Delayed processing of Vector / Matrix expression in Julia with various backends.
  • JSparse.jl :: A Julia implementation of functions in the CSparse and CXSparse libraries developed by Tim Davis.
  • KSVD.jl :: K-SVD is an algorithm for creating overcomplete dictionaries for sparse representations.
  • MappedArrays.jl :: Lazy in-place transformations of arrays.
  • RandomBandedMatrices.jl.
  • Ranges.jl :: Array-like objects with compact storage for the Julia language.
  • RangeArrays.jl :: Efficient and convenient array data structures where the columns of the arrays are generated (on the fly) by Ranges.
  • RingArrays.jl :: A sliding window over a huge array.
  • Showoff.jl :: Nicely format an array of n things for tables and plots.
  • SizeArrays.jl :: Julia array parametrised by size instead of dimension.
  • StructsOfArrays.jl :: Structures of Arrays that behave like Arrays of Structures.
  • SoArrays.jl :: Structures of Arrays that behave like Arrays of Structures.
  • StaticArrays.jl :: Statically sized arrays for Julia v0.5.
  • SymDict.jl :: Dictionaries with Symbol keys.
  • TimeArrays.jl :: A temporary repo exploring the union of SeriesPair arrays into multicolumn arrays with similar behavior.
  • WoodburyMatrices.jl :: Library support for the Woodbury matrix identity.
  • WSMP.jl :: Interface to the Watson Sparse Matrix Package.

[Graphs](Hash tables / Linked List / Functional / Trees data structures)

  • AbstractTrees.jl :: Abstract julia interfaces for working with trees.
  • Arrowhead.jl :: Arrowhead and Diagonal-plus-rank-one Eigenvalue Solvers.
  • ASTInterpreter.jl :: Gallium's AST interpreter as a separate package to simplify development.
  • BGraph.jl :: An adjacency list that uses typed properties for vertices, edges, and graphs.
  • BlockArrays.jl :: BlockArrays for Julia.
  • bloom.jl :: Bloom filter implementation in Julia.
  • BloomFilters.jl :: are a probabilistic data structure that can be used to test the inclusion and exclusion of items in a list.
  • Blox.jl :: Views of concatenated AbstractArrays in Julia. {Usable: 2, Robust: 2, Active: 1}
  • Brim.jl :: BRIM modularity - Various ways to optimize the modularity of bipartite networks using BRIM in Julia.
  • CompressedStacks.jl
  • DeepReshapes.jl :: Reshape arbitrarily nested structures of Tuples and Arrays in Julia.
  • EvolvingGraphs.jl :: Dynamic Graph Analysis Framework in Julia.
  • FingerTrees.jl :: A Finger Tree is a functional data structure that can give an amortized constant time access to the fingers (leaves) of the tree where the data is stored, while the internal nodes are labeled in some way as to provide the functionality of the particular data structure being implemented.
  • Flow.jl :: DataFlow programming for Julia.
  • FunctionalCollections.jl :: Functional and and persistent data structures for Julia.
  • Graphs.jl :: a package for working with graph types and algorithms in Julia.
  • GraphLayout.jl :: Graph layout algorithms in pure Julia.
  • GraphicalModels.jl :: Data structures and parsing tools for representing graphical models in Julia.
  • InfoTheory.jl :: Estimating information theoretic measures (entropy, mutual information etc) from data.
  • InvariantEnsembles.jl :: Sample random unitary invariant ensembles.
  • L1DecisionTree.jl
  • LiftedHierarchies.jl.
  • LightGraphs.jl :: An optimized simple graphs package designed for fast analysis using standard functions that seeks to mimic the functionality of established packages like NetworkX, but with better performance.
  • Lists.jl :: Singly linked list and doubly linked list for Julia.
  • LSH.jl :: Locality Sensitive Hashing functions.
  • MatrixNetworks.jl :: Graph and Network algorithms.
  • MatrixDepot.jl :: A multi-language collection of test matrices for Julia. Documentation
  • MinimalPerfectHashes.jl :: An implementation of minimal perfect hash function generation as described in Czech et. al. 1992. http:https://bit.ly/137iukS
  • Named.jl :: Julia named index and named vector types.
  • NamedArrays.jl :: Julia type that implements a drop-in replacement of Array with named dimensions and Dict-type indexes.
  • NamedAxesArrays.jl :: Performant arrays where each axis can be named.
  • NamedTuples.jl :: Provides a high performance implementation of named tuples for Julia (cf named tuples in python).
  • Networks.jl :: A library for working with Graphs in Julia.
  • OffsetArrays.jl :: Negative Indexing - it provides the ability to use arbitrary starting indices for arrays in Julia. The main purpose of this package is to simplify translation from Fortran codes intensively using Fortran arrays with negative and zero starting indices, such as the codes accompanying the book Numerical Solution of Hyperbolic Partial Differential Equations by prof. John A. Trangenstein.
  • Graft.jl :: A graph analysis toolkit for Julia that stores vertex and edge metadata in separate dataframes.
  • PDMats.jl :: Uniform Interface for positive definite matrices of various structures.
  • PositiveFactorizations.jl :: Positive-definite (approximations) to matrices.
  • PropertyGraph.jl :: A Julia package for constructing, creating and querying graph data structures.
  • QuickStructs.jl :: Several data structures with goals of O(1) for important operations. {Usable: 5, Robust: 4, Active: 1}
  • RandomForestBehaviors.jl :: Microscopic driving models based on random forests.
  • RedBlackTrees.jl :: A red–black self-balancing binary search tree in Julia. REF: http:https://en.wikipedia.org/wiki/Red_black_trees
  • RepresentationTheory.jl :: Kronecker product of Sn.
  • RingBuffer.jl :: Julia ring buffer implementation for buffered IO.
  • RobustShortestPath.jl :: Robust Shortest Path Finder.
  • rsk :: Code for exploring the Robinson–Schensted–Knuth correspondence.
  • Seep.jl :: It builds and evaluates computational flow graphs in julia. A computational flow graph (CFG) is a directed acyclic graph where nodes represent values and edges represent data dependencies.
  • Series.jl :: Series data structure in Julia.
  • SFrames.jl :: Wrapper around the open-source components of Graphlab.
  • SimpleGraphs.jl :: A module for working with simple graphs (no loops, no multiple edges, no directed edges).
  • Sims.jl :: Non-causal, equation-based modeling in Julia.
  • SpatialGraphs.jl
  • SuffixArrays.jl :: Native Julia suffix array implementation. Derived from sais.
  • SumTrees.jl :: Binary tree where the nodes contain the sum of the left and right children.
  • Trie.jl :: Implementation of the trie data structure.
  • TSPSubgradient.jl :: A TSP approximation with the subgradient method.
  • XGBoost.jl :: XGBoost Julia Package.

Publications

RESOURCES